حل مساله کوله پشتی با رویکرد حریصانه

صفحه 1:


صفحه 2:
اهداف درس این جلسه حل مساله کوله پشتی با رویکرد حریصانه مقایسه رویکرد حربصانه با برنامه‌نویسی پویا در حل مساله 

صفحه 3:
یادآوری مسئله کوله پشتی صفر و یک 0 ‎w; = weight of item;‏ ‎Pi = profit of item;‏ ‎W = maximum weight the knapsack can hold‏ که ,۷۷ و ,0 و ۷۷ همگی اعداد مثبتی هستند. می‌خواهیم زیر مجموعه ۸ از 5 را به گونه‌ای مشخص کنیم که ... 2 Pi is maximized subject to ۳13 ‏:نا‎ > ۷ و ۰4 

صفحه 4:
۰) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک اگر بخواهیم رویکرد 0۲۱16-۲0۲۳6 ما درنظر بگیریم ... باید تمامی زیرمجموعه‌های 5 را درنظر بگیریم و .. از اونهایی که مجموع وزنشون از ‎W‏ بیشتر است صرفنظر کنیم و ... از زیرمجموعه‌های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم. پیچیدگی محاسباتی اين روش بادرنظر گرفتن ‎٩‏ آیتم ... asl ‏مين‎ 7 

صفحه 5:
۰) الگوربتم حریصانه در مسئله کوله پشتی صفر و یک اولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که.. تمامی آیتم‌ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ... به ترتیب آیتم‌ها را از مجموعه مرتب‌شده برداریم مادامیکه ... مجموع وزنشان از ۷۷ بیشتر نشود. این استراتژی زمانیکه آیتم‌های با منفعت بالا وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی‌باشد. 

صفحه 6:
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک احتمالا استراتزی بعدی اين می‌تواند باشد که آیتم‌های سبک‌تر را ابتدا برداریم ~ این استراتژزی هم زمانی که آیتم‌های سبک منفعت کمی داشته باشند به شکست می‌انجامد. 

صفحه 7:
۰) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک راه حل حریصانه مناسب این است که ... آیتم‌ها را بر اساین منفعت واحد وزنشان به صورت نزولی مرثب کنیم 3 1 بت را تا زمانیکه مجموع وزنشان از ۷۷ بیشتر نشود برداریم. 

صفحه 8:
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک بو فد و و 5 :۶ 810 < item, : 5 30 Ib $140 Max. ‘$60 Le] a Item 1 ttem 2 ttem 3 Knapsack Greedy Optimal solution solution 

صفحه 9:
۰) الگوریتم حریصانه در مسئله کوله پشتی کسری ‎(Fractional)‏ در مساله کوله پشتی کسری چنانچه برداشتن کل آیتم میسر نیست. می‌توان بخشی از آن را نیز برداشت. مثلا در مثال قبل ... ۰ $50 + $140 + 10 ($60) = $220. بنابراین هیچ فضایی هدر نمی‌رود. پس همواره حل بهینه را خواهیم داشت. 

صفحه 10:
۰) برنامه نوبسی پوبا در مسئله کوله پشتی صفر و یک اصل بهینگی را در مساله کولهپشتی صفر و یک نشان دهیم... بنابراین می‌توانیم آن را با برنامه‌نویسی پویا حل کنیم. 

صفحه 11:
0( برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یک يادآورى اصل بهينكى 6ه عاماءصاءص ‎(Optimality‏ مساله‌ای شرایط اصل بهینگی را دارد چنانچه در آن مساله ... زیر راه‌حل‌های یک راه‌حل بهینه برای هر نمونه مساله ... خودشان راه‌حل‌های بهینه برای زیرمسائلی متناظر باشند. 

صفحه 12:
۰) برنامه‌نوبسی پوبا در مسئله کوله پشتی صفر و یک فرض کنیم که ۷ زیرمجموعه بهینه شامل ۲۱ آیتم باشد ... باید نشان دهیم زیر راه‌حل‌های بهینه این راه حل بهینه خود حل‌های بهینه برای زیر مسائل متناظرشان هستند. در اینجا دو امکان وجود دارد ... پا ۵ شامل ,66019 است يا نیست. 0 

صفحه 13:
0( برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یک اگر ۸ شامل ,766/11 ‎wos‏ بنابراین ... ‎A‏ دربرگیرنده پاسخ بهینه (زیر رلم حل برلی0-1 آیتم (زیر مساه) ميماشد ‏اگر (/ شامل بر66111/ باشد ... ‏بنابراین مجموع منفعت‌های بدست آمده در / برابر است با م2 به اضافه ... منفعت بهینه بدست آمده از انتخاب 2-1 آیتم اول .. ‏البته با اين محدودیت که ... ‏مجموع وزن ۱-1 آیتم اول از .. ‏۷-۷۷ بیشتر نشود. ‏پس اصل بهینگی برقرار است ‎ ‎ ‎ 

صفحه 14:
۰) برنامه‌نوبسی پوبا در مسئله کوله پشتی صفر و یک برای حل مساله با رویکرد برنامه نویسی پویا همانند گذشته باید ... ویژگی بازگشتی تعریف کنیم که حل مساله از پایین به بالا ایجاد شود. ابتدا راه حل بهینه برای زمانیکه که ۸۸ دارای ۱ آیتم» سپس ‎A‏ دارای ... ۲ آیتم. سپس دارای ۳ آیتم و ... در نهایت ۸۵ دارای "۲ آیتم باشد. 

صفحه 15:
) برنامه نويسى يويا در مسئله كوله يشتى صفر و یک ماتريس ”ا را درنظر مى كيريم كه [//ا]/]5 برابر است با ... منفعت بهينه زمانى باشد كه ... أ ليتملبتطليىب اليزشرط كه مجموع وننشازاز الا تجوز نكند توجه: آيتمهاى ليست بر اساس نسبت منفعت به وزن مرتب شدهاند. م > بس كذ (رسد- ص] [1 - ف] 2 + رع ؛ [س] [1 - ن] ط) سم إس] إنام ‎Pli-1 [wl if w > w‏ ... ‏پاسخ نهایی‎ sly P[n][W] Ke 

صفحه 16:
۰) برنامه نوبسی پوبا در مسئله کوله پشتی صفر و یک مک رگا (إرس-ص] لا - تاه + ‎marina (PEM lu].p.‏ { = زیر ‎w.‏ < رنه از (س] (۱- نا بنابراین ماتریس ۳ بايد داراى سطرهايى با انديس ۰ تا 0 باشد. باید دارای ستون‌هایی با اندیس ۰ تا ۷۷ باشد تا ... بر اساس رابطه با زگشتی تعریف شده. المان‌های ماتریس را محاسبه کنیم تا در نهایت ... ‎P[n][W]‏ محاسبه شود. ‏مقادیر ‎P[O][w]‏ و ‎P[i][0]‏ پیش‌فرض برابر ۰ قرارداده می‌شود. ‎ ‎ ‎ ‎ 

صفحه 17:
۰) روش بهبودبافته برنامه‌نویسی پویا در سنده وله بشتی مفرویک با اين روش حل, پیچیدگی محاسباتی هم به ۲۱ و هم به .. ۷ بستگي‌دارد. اگر مجبور باشیم تمامی المان‌های ماتریس را محاسه کنیم در این صورت باید .. ۷ محاسبه لنجام دهیم که روش‌ما داری‌مرتبه پیچید گی‌محاسباتی(9)۳۷۷ خوهد بود که ... به ۷۷ وابسته است که اگر ۷۷ مقادیر بزرگ مثلا ۱0 داشته باشد در این صورت ... مثلا برای ۲20 اجرای الگوریتم سال‌ها به طول خواهد کشید. در این حالت .. این الگوریتم از الگوریتم 0۳66 0۲۱06 که دارای پیچیدگی .. 7 بود بدتر مهاشد 

صفحه 18:
۰) روش بهبودیافته برنامه نویسی پویا در سنده کوله پشتی مفرویک ۲ نم ۱۳۹۳۳۱۳۱ لب رتور مرح ‎if wy > W,‏ (1(۱۲ مام الگوریتم را می‌توانیم به گونه‌ای تغییر دهیم که پیچیدگی محاسبات کاهش پابد. چگونه؟ این واقعیت وجود دارد که نیازی نیست که مثلا در سطر أء مقادير تمامی ستون‌ها از ۱ تا ۷۷ محاسبه شود. مثلا تنها المان‌هایی که نیاز است در سطر ۲-1 ام محاسبه شود ... P[n—1)(W] and P{n-1](W —w,] 

صفحه 19:
۰) روش بهبودیافته برنامه‌نویسی پوبا در سنه كوله يشتى صفرويى بنابراین تعداد المان‌هایی از ماتریس که نیاز است محاسبه شود برابر 1 - 2۳ 2۳71 + ...+ 22 +1424 ©