مسئله کوله پشتی صفر و یک

صفحه 1:
لباوب 11111 : مراحل بيش رو لكوتم عقبكرد بسرلومسئله كوله بشتوصفر و بكه1 عقليسه لكوربتم بويا و عقبكرد براهسئله كوله بسشتوسفر و -2 یک 

صفحه 2:
اا 1۳ مسئله کوله پشتی صفر و یک در لین مسئله مجموعه ای از قطعات را دارییم که هر یک دارای وزن و ارزش معین است وزن ها و ارزش ها اعداد صحیح مثبت . دزدی قصد دارد قطعاتی را که عی دزدد درونیک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در کوله پشتی ازبیک عدد صحیح ۷1 فرلتر رود کوله پشتی پاره ی شود . هدف تعیین مجموعه ای از قطعات است که ارزش کل قطعات را بيشينه مى كند به طوری که وزن کل آن ها از ۷/۷ ب نشود. Item, Item; ....ltemn} wj = Weight of item; Pj = Profit of item; 

صفحه 3:
اا 1۳ مسئله کوله پشتی صفر و یک به روش عقبگرد مسئله را به صورت زیر به صورت یک مثال : فرض کنیم . (:۱6 روهار 5-60 خت در می اوریم. هنكامى كه از ريشه به سمت جب مى رويم نخستين قطعه در مجموعه قرار مى كيرد واكراز ريشه به سمت راست_حركت كنيم قطعه اول در مجموعه قرار نمى كيرد. در سطح دوم نیز اگر از یک گره به سمت چپ حرکت کنیم قطعه دوم در مجموعه قرار مى كيرد و اكر به سمت راست حركت كنيم اين قطعه در مجموعه قرار نمى كيرد. در ساير سطوح نيز به همين صورت مى باشد. 

صفحه 4:
[۱۳ نکته حائز اهمیت در اين مساله این است که تا زمانی که جستجو به پایان نرسد نمی توان دریافت گره ای حاوی یک حل می باشد یا خیر. در مثال بهتر متوجه میشوید . 

صفحه 5:
مثال: فرض کنید 16,۴4 < ۷۷ و داشته باشیم : Pi 1 Pi WY 7 1 $40 2 $20 2 $30 5 $6 3 850 10 $5 4 $10 5 $2 قطعات از قبل بر اساسر ,۳:/1 مرتب شده اند 1117 يي ۱۳ 

صفحه 6:
ااا ابتدا با جند تعريف آشنا مى شويم :5577 إيعنى بهترين مسيرى كه در درخت بيموده ايم)) :بهترين مجموعه اى كه تا به حال انتخاب كرده ايم ‎SET:‏ BEST SET Js .45,1Max profit: ‏:مجموعه ی لنتخابی‌در هر مرحله (مسیریکه ا-ا‌در نود لنتهای‌آن‌ستیم),‎ 6 ‏مجموعه‎ JS 339: Include weight ‏زش كل‎ include Ow) : bound ‏فرض می کنیم در گره ای واقع در سطح 1 قرار داریم و گره ی واقع در سطح 1 گره ای است که‎ : ‏حاصل جمع اوزان را از بيشتر ميكند در اين صورت‎ ۱ 

صفحه 7:
totweight = weight + >" wy ore k-1 bound = (profit + 1 p;) + (W - totweight) x Pe — k 1 Profitfrom first k-1 Capacity available forkth Items taken item این فرمول به ما می گوید بهترین سودی که در اين مرحله در ذهن ما می گنجد داشته باشیم جقدر است به این صورت که ما نمی توانیم عنصر سطح ‏ را برداريم چون در صورت انتخاب ان مجموع وزنها از ما بيشتر میشود ولی فرض میکنیم که ما میتوانیم به اندازه ای که کوله ی ما جا دارد بخشی از آن را برداریم لذا بهترین سود فرضی ما در هر مرحله است . در هر مرحله بايستى انرا محاسبه نمالیم در ادامه بهتر متوجه ميشويد EE 

صفحه 8:
مثال: فرض کنید 16,۴4 < ۷۷ و داشته باشیم : Pi 1 Pi WY 7 1 $40 2 $20 2 $30 5 $6 3 850 10 $5 4 $10 5 $2 قطعات از قبل بر اساسر ,۳:/1 مرتب شده اند 1117 يي ۱۳ 

صفحه 9:
در هر دایره عدد بالایی جمع اوزان انتخابی و عدد سوم ع :525227771144ئتئتت ۱ 

صفحه 10:
: شرايط اميد بخش بودن بید بخش بودن یک گره یعنی با توجه به مجموعه ى عو لااع أ بتوانیم شی دیگری را انتخاب کنیم و ازاین گره عبور کنیم (یعنی امید ملاقات گره های دیگر وجود داشته باشد). weight < w Max profit < bound شرایط انتخاب یک گره به عنوان گره پایانی(یعنی مجموعه ای که انتخاب کرده ایم» بهتر از مجموعه ی ]ع 655 است): Weight <= w [ Profit > max profit 

صفحه 11:
Best set :{} Max Profit : 0 

صفحه 12:
EE - گره (۰,۰) را ملاقات می کنیم . - ارزش و وزن آن را محاسبه می کنیم(که برابر است با ارزش و وزن مجموعه ای که فعلا انتخاب کرده ایم (مجموعه 18610106 )) ( یعنی ارزش و وزن کل مسیری که منتیهی به اين گره میشود) : ‎Profit=0 , weight=0‏ -مقدار 12001110101 (حد) را محاسبه می کنیم: در سطح 623 داریم : مجموع وزن های انتخابی از سطح 120 برابر است با: ۱۷-۱۰+۵+۲ که ۱۷ ۷۷16 بو ‎iotweight = weight ++ J wj=0424+5=7‏ ‎ston‏ at bound | profit + S> pj +(W — totweight) x 2 ‏0+1در‎ 56 $50 = 80 + $40 4 $30 4 (16 ~7) ‏و‎ = SIS. weight <W and bound > maxprofit => nodeis promising 

صفحه 13:
شی‌اول Maxprofit : 0 Include { item 1} Profit : 40 Weight : 2 Bound :115 

صفحه 14:
ee EE ‎maxprofit= 0‏ ۳- گره‌ط۱:۱) را ملاقات می کنیم . "ارزش و وزن آن را محاسبه مى كنيم : ‎profit=$0+$40=$40 ‎weight=0+2=2 ‏-مقدار 190121201 (حد) را محاسبه می کنیم: ۰ ۱۶>۱۷ 3= 5-7 +22 وله = + ‎totweight = weight‏ ده ‎bound = profit+ > pj + (W —totweight) x 2‏ ‎iam‏ ‎x = = 8115.‏ )7 — 16( + $30 + $40 = ‎weight <W and bound > maxprofit => nodeis promising ‎ 

صفحه 15:
Include : {item1,item2} Profit : 70 Weight : 7 Bound :115 ‏مم‎ Profit > max profit , weight<W Best , Max profit=70 تور رم ]۳ © 6 3 el 

صفحه 16:
1111133 بي ‎maxprofit= $40‏ ‎(Tle 5 -F‏ را ملاقات می کنیم. "ارزش و وزن آن را محاسبه می کنیم ‎profit=$40+$30=$70 ‎weight=2+5=7 ‏-مقدار 190121001 (حد) را محاسبه می کنیم: ‎at‏ ‎totweight = weight + 2 wy ‏کر‎ ‎ ‎ ‎bound = $70 + (16 —7) x 0 = $115 ‎weight <W and bound > maxprofit => nodeis promising ‏ل 

صفحه 17:
Best set : {item1,item2} Max profit: 70 Include : {item1,item2,item3} Profit : 120 Weight : 17 Profit > max profit , weight<W=16 

صفحه 18:
۳ ‎maxprofit= $70‏ ۵- گرهد۳,۱) را ملاقات می کنیم. ‏"ارزش و وزن آن را محاسبه مى كنيم : 120 ‎ ‎profit=$70+$50: ‎weight=7+10=17 ‏چون ۱۷ از مقدار 1۷ یعنی ۱۶ بزرگتر می باشد این گره اصلا نمی تواند اتخاب شود ‏۶- عقبگرد به گرهطا:۲) ‎ 

صفحه 19:
6 ‏الور تا توت متا‎ Max profit : 70 Include : {item1,item2} ار 70 : ‎Profit‏ ‎Bound :80 profit > max profit‏ ‎rofit = MareproGitsba 4S 5 shila:‏ ‎Weight <=W‏ لذا كره(©و0) انتخاب نميشود و در مجموعه اتخابها قرار نمی گیرد ولی این مر كره شرايط اميد بخش بودن را دارد لذا فرزندان اين كره را بررسى ميكنيم 

صفحه 20:
‎maxprofit= $70‏ ۷- گره(۳,۲) را ملاقات می کنیم . "ارزش و وزن آن را محاسبه مى كنيم : ‎profit=$70 ‎weight=7 ‏نکته مهم : ‏-چون وزن چهارم باعث نمی شود که حاصل جمع قطعات از ۷ بیشتر شود و فقط ۴ قطعه وجود دارد بنابراین :1625 5-1 .$80 = $10 + $70 = رم + ‎bound = profit‏ ادر ‎weight <W and bound > maxprofit => nodeis promising ‎EE 

صفحه 21:
best set}item1,item2} sMax profit : 70 Include : {item1,item2,item4} Profit: 80 5 Bound :80 Profit > max profit , weight<W > best set}item1,item2,item4} , Max profit=80 ‏بس امید‎ » 0۲۵۶3۲ < bound ‏بس اين كره انتخاب می شود ولی چون‎ ‏بخش نیست . به طور شهودی هم این گره اصلا فرزندی ندارد که ما بخواهیم‎ ‏بررسی کنیم لذا اين كره غير اميد بخش است.‎ ۳۹9 $30 2 um [55 5 

صفحه 22:
لباوب 11111 maxprofit= $70 ۸- گرهد۴,۱) را ملاقات می کنیم. ‎profit=$80, weight=12‏ profit > maxprofit > maxprofit= $80 bound=$80 Bound=maxprofit node is nonpromising ‎-٩‏ گره‌۴,۲۵) نیز غیر امیدبخش می باشد. ‎ 

صفحه 23:
توضیح مهم همانطو رکه در اسلایدهای اولیه گفتیم جواب نهایی را وقتی معین می کنیم که جستجو در در خت بایان بپذیرد. در صورتی که ما تا الآن تنها چند مسیر را پیمودیم. در این مسیرها ما بهماکزیمم ارزشی معادل 5۸۰ دست یفته ام ‎est‏ ‏پس به عقب بر میگردیم و مسیرهای دیگر را بررسی میکنیم 561 اگر مسیرهای دیگر ارزشی بیشتر از 9۸۰ به ما داد , ما مجموعه 4 آپدیت میکنیم. یعنی مسیری که سود بیشتری به ما میدهد در قرار میگیرد لذا بهکره "(1 وا اعقب گرد می کنیم. ———————— 6:6١ 

صفحه 24:
: به كره (0و0) برميكرديم و به كره (©ر©) مى رسيم و داريم best set}item1,item2,item4} Max profit : 80 Include : {item1,item3} Profit : 40 +50= 90 Bound :98 Profit > max profit , weight<W > best set}item1,item3} , Max profit=90 

صفحه 25:
در این گونه در خت ها تمام مسیرها را از نود شروع تا برگ میرویم به این صورت که ابتدا یک مسیر تا اخر میرویم سپس نتیجه را ثبت میکنیم سپس پله به پله بر میگردیم عقب و مسیر دیگری را بررسی میکنیم اگر به ارزش بیشتری رسیدیم مجموعه انتخاب بهتر را برمی گزینیم در این درخت جواب نهایی مسیر ابی است ولی ما باید به همین ترتیب گفته شده کل مسیرها را بررسی میا ‎ea‏ رديه جم 

صفحه 26:
ee الكوريتم عقبكرد براى مسئله كوله يشتى صفر و یک void knapsack (index i,int profit, int veight) ‘ if (veight <= ‏وعم‎ profit > maxprofit){ // This set is best maxprofit = profit: // 30 far. numbest = i; // Set numbest to bestset = include; // number of items 0 // considered. Set // bestset to this 77 solution. if (promising (i)){ include [i + 1] = "yes"; // Include v[i + 1). knapsack(i + 1, profit + pli +1], veight + v[i + 11): include [i + 1] = "no": 77 Do not include knapsack (i + 1, profit, veight): . 7 vli + 11. 

صفحه 27:
الگوریتمعقبگرد برای مسئله کوله پشتی صفر و یک bool promising (index 2) 4 index 3: Ant totvezaat: ar (weigar >= 9) ‏زز‎ nose 29 promising ony ‏ممعم‎ fates Y) 48 we whould expand 2 else { 1 v0 children. There must ‎Y/ ve zone capacity ett for‏ ود مدع و ‎ ‎bound = profits W/ the children, ‎rotveight ~ veigat: ‎wnile (j <= 2 G6 cocveigar + ‏رتاس‎ > Grab as many items as ‎ ‎ ‎totweigat ~ tosveigat + ¥{317 possible, pound = ound ~ B(J)? gee , ani ‏رز‎ vse x tox consistency if (Fenn) Y/ with formule in text ‎bound ~ hound + (W - tobveight) * ‏لا« لقاع‎ J/ Gasp fzacticn of kth ‎return bound > maxprofits ۱۱ ‏بععد‎ 

صفحه 28:
ee الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک numbest maxprofit = 07 knapsack (0, 0, ۶ cout << maxprofit; for (j = 1; j <= numbest; j++) cout << bestset{i]: 

صفحه 29:
ee مقايسه الكوريتم بويا و عقبکرد برای مسئله وله پشتی صفر و یک اجرای مسئله در بدترین حالت با الگوریتم پویا O (minimum (22, nW)). اجرای مسئله در بدترین حالت با الگوریتم عقبگرد © )20 الگوریتم های عقبگرد در بدترین حالت .دید خوبی نسبت به کارصرفه جویی شده نمی دهند هور و شانی در سال 18۹۷۸با اجرای الگوریتم های عقبگرد و پویا بر روی چندین نمونه نشان دادند که الگوریتم عقبگرد در مقایسه با الگوریتم پویا کارایی بیشتری دارد