من با راه حل کوله پشتی 0/1 مشکل دارم
میشه این سؤال رو حل کنید:
5 شی داریم با وزن‌ها و ارزش های زیر:
p1=35
w1=7
p2=30
w2=5
p3=20
w3=2
p4=12
w4=3
p5=3
w5=1
ظرفیت کوله پشتی 13 است. مقدار سود ماکزیمم چقدر است؟
65
68
70
80
سوال IT85
تو کتابا با نگرش مجموعه ای حل کرده راه حلی طولانی و بدفهم
لطفا یه جور بگین که بفهمم چی شد ساده و خلاصه (به قول معروف کنکوری
)
مرسی
خوب کوله پشتی صفر و یک به روشهای مختلفی حل میشه که من فقط حریصانه رو بلدم که همیشه هم جواب بهینه نمیده!
شما اول باید سود واحد هر شی رو بدست بیارید.( تا بفهمید ارزش بر گرم یا کیلوگرم یک شی چقدره)
بعد اونها رو برحسب سود واحد به صورت نزولی مرتب کنید بعد یکی یکی انتخاب کنید و ارزش و وزنش رو جمع بزنید هرکدوم که باعث شد وزن از حد مجاز بیشتر بشه بیخیال بشین و برید سراغ بعدی.
مثلا p1 سود واحد (که من با Ci نشون میدم) برابر 5 داره.
c1=5
c2=6
c3=10
c4=4
c5=3
مرتب میکنیم بعد اول c3 انتخاب میشه وزن میشه 2 بعد C2 وزن میشه 2+5 و بعد C1 وزن میشه 14 پس C1 رو بیخیال میریم بعدی C4 وزن میشه 10 و بعد c5 و وزن میشه 11 و چون کوله پشتی پر نشد پس این جواب الزاما بهینه نیست!
پس ارزشها رو جمع میزنیم (Pها ):20+30+12+3 =65
چون روش کوله پشتی صفر و یک چون حریصانه است الزاما جواب بهینه رو نمیده!!!
اینبار هم همینطوره چون جواب حل بهینه میشه برداشتن اشیا اول و دوم و پنجم که جمع ارزش میشه 68!
من خودم این روش را بلدم ولی این برای کوله پشتی 0/1 راه حل خوبی نیست
باید از پرنامه نویسی پویا استفاده کنیم
جواب هم نه 65 نه 68
کلید جواب 70 است!!!
کسی راه حلشو بلده؟؟؟؟؟؟؟
(16 دى 1389 09:32 ب.ظ)afagh1389 نوشته شده توسط: [ -> ]خوب کوله پشتی صفر و یک به روشهای مختلفی حل میشه که من فقط حریصانه رو بلدم که همیشه هم جواب بهینه نمیده!
آفاق عزیز معلومه که روش حریصانه درست نیست چونکه حریصانه فقط برای بهینه سازی محلیه ونمی تواند جواب بهینه نهایی رو بده، اما اگه کوله پشتی کسری بود روش حل بهینه محلی و سراسری یکی بود . اما در کوله پشتی صفر و یک باید مسئله رو به زیر مسائل بهینه تقسیم کنیم به نحوی که ترکیب این زیر پاسخ‌ها به جواب بهینه برسه( خصیصه الگوریتم های پویا)
اما جواب مقدار 70 هست چراکه
گزینه 4 با مقدار 80: باید برای سود 80 اشیا با وزنهای 35 و 30 و12 و 3
انتخاب بشه (هیچ راهی دیگه نداریم که مجموع 80 بشه، اما اگه وزن قطعات متناظر با سود داده شده بررسی کنیم میشه 16 پس توی کوله جا نمیشه
بریم روی گزینه 3 با مقدار 70: همه اشیا غیر 2 انتخاب میشه با ارزش 70 و وزن 13 و از آنجا که 70 از مقدار گزینه 1و 2 بیشتره پس جواب همینه
اینم راه حل تستی
امیدوارم جواب گرفته باشید.
با سلام
من کد کوله پشتی 0و1 رو میخواهم
با تشکر