پاورپوینت مسأله مجموع زیرمجموعه ها
| دسته بندی | علوم پایه |
| بازدید ها | 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