پاورپوینت مسأله مجموع زیرمجموعه ها
- موضوع : ریاضی
- فرمت اصلی فایل : pptx
- تعداد صفحات : 10
- حجم فایل: 66.15722656 mb
پاورپوینت مسأله مجموع زیرمجموعه ها
قسمتی از متن
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”
فهرست مطالب:
مسأله مجموع زیرمجموعه ها
درخت فضای حالت (n=3, M=6, w=(2,4,5
حل مسأله
درخت فضای حالت برای n=5, M=21, w=(5,6,10,11,16
الگوریتم مجموع زیرمجموعه ها
مسأله چرخه هامیلتونی
روش حل
الگوریتم چرخه هامیلتونی
تحلیل پیچیدگی زمانی
