• پاورپوینت مسأله مجموع زیرمجموعه ها

• موضوع : ریاضی
• فرمت اصلی فایل : 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[1n] : در صورتی که عدد 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
الگوریتم مجموع زیرمجموعه ها
مسأله چرخه هامیلتونی
روش حل
الگوریتم چرخه هامیلتونی
تحلیل پیچیدگی زمانی