پاورپوینت مسأله مجموع زیرمجموعه ها
| دسته بندی | علوم پایه |
| بازدید ها | 1 |
| فرمت فایل | ppt |
| حجم فایل | 17 کیلو بایت |
| تعداد صفحات فایل | 10 |
پاورپوینت مسأله مجموع زیرمجموعه ها
پاورپوینت مسأله مجموع زیرمجموعه ها دارای 10اسلاید با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید.
n عدد صحیح مثبت wi و یک عدد صحیح مثبت M وجود دارد. هدف یافتن تمام زیرمجموعه های اعداد صحیح است به طوری که مجموع آنها M باشد.
مثال:
n=5, M=21, w=(11,5,6,16,10)
5+6+10=21, 5+16=21, 10+11=21
حل با استفاده از روش ایجاد درخت فضای حالت
حل مسأله
برای تعیین گره های وعده گاه اعداد را به صورت غیرنزولی مرتب می کنیم.
در سطح i ام , wi+1 کمترین وزن باقی مانده را دارد.
اگر weight مجموع اعداد تا گره سطح i باشد:
weight+ wi+1 >M ام غیر وعده گاه i گره
اگر total مجموع اعداد باقی مانده باشد:
weight+ total >M ام غیر وعده گاه i گره
اگر weight=M آنگاه یک جواب در آن گره به دست آمده و باید به عقب برگشت و مسیر جدید را شروع کرد.
آرایه include[1..n] : در صورتی که عدد iام انتخاب شود include[i]=“yes” در غیر اینصورت include[i]=“no”
الگوریتم مجموع زیرمجموعه ها
void sos(int i, int weight, int total)
{ if (promising(i))
if (weight = = M)
cout<
else
{ include[i+1]=“yes”;
sos(i+1,weight+w[i+1],total-w[i+1]);
include[i+1]=“no”;
sos(i+1,weight,total-w[i+1]);
}
} total= w[j], sos(0,0,total) فراخوانی اولیه
int promising (int i)
{
return(weight+total>=M) && (weight= =M || weight+w[i+1]<=M);
روش حل
گره شروع در سطح صفر درخت
در سطح یک همه گره ها به جز گره شروع
در سطح n-1 همه گره ها به جز سطوح قبل
نکات:
i امین گره همجوار گره i-1 ام باشد
n-1 امین گره مجاور گره صفر (شروع) باشد.
i امین گره نباید برابر با i-1 گره قبل باشد.
آرایه vindex[0..n-1] از شاخص های گره ها مسیر را نگهداری می کند
تعداد گره های درخت فضای حالت:
1 + (n-1) + (n-1)2+… +(n-1)n-1=
ppt: نوع فایل
سایز: 17.1 KB
تعداد اسلاید:10
پاورپوینت مسأله کوله پشتی 1-0 با روش backtracking
| دسته بندی | علوم پایه |
| بازدید ها | 1 |
| فرمت فایل | ppt |
| حجم فایل | 18 کیلو بایت |
| تعداد صفحات فایل | 7 |
پاورپوینت مسأله کوله پشتی 1-0 با روش backtracking
پاورپوینت مسأله کوله پشتی 1-0 با روش backtracking دارای 7 اسلاید با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید.
حل مسأله با استفاده از درخت فضای حالت
تا پایان جستجو امکان فهمیدن این که آیا یک گره جواب است یا خیر وجود ندارد.
باید بهینه سازی را درنظر داشت. اگر مجموع ارزش گره ها بیشتر از بهترین جوابی باشد که تا کنون به دست آورده ایم, مقدار بهترین جواب را به مقدار جدید تغییر می دهیم.
فرض: weight: مجموع وزن کالاهایی که تاکنون به گره ای اضافه شده اند.
profit : مجموع ارزش کالاهایی که تا گرعه جاری به حساب آمده اند.
bound: یک حد بالا برای ارزشی که می توانیم با بسط گره به آن برسیم.
totweight: حداکثر وزن کالاهای قابل انتخاب
maxprofit: مقدار ارزش بهترین جوابی که تا کنون پیدا شده.
کالاها را به صورت غیرنزولی بر اساس مقادیر pi / wi مرتب می کنیم.
گره سطح k : گرهی که موجب تجاوز مجموع وزن از مرز M می شود.
در سطح i پیش بینی از حداکثر ارزش قابل دستیابی, برابر با مجموع ارزش به دست آمده به علاوه ارزش کالاهای باقی مانده تا سطح k-1 به علاوه مقدار قابل انتخاب از کالای k ام (با فرض این که بتوان بخشی از آن را انتخاب کرد) می باشد.
bound ≤ maxprofit : گره غیر وعده گاه است.
الگوریتم مسأله کوله پشتی با روش backtracking
void knapsack(int i, int profit, int weight)
{ if weight <= M && profit > maxprofit)
{ maxprofit=profit;
numbest=i;
bestset=include;
}
if (promising (i))
{ include[i+1]=“yes”;
knapsack(i+1, profit+p[i+1],weight+w[i+1]);
include[i+1]=“no”;
knapsack(i+1, profit,weight);
}
ppt: نوع فایل
سایز:18.8 KB
تعداد اسلاید:7