يعني به او بگوييم چه وسايلي را به ترتيب بردارد كه علاوه بر ارزش بالايشان، حجم آنها طوري باشد كه در كوله‌پشتي‌اش جا شوند.
روش حريصانه براي حل اين مساله
در اين روش 2 حالت را در نظر مي‌گيريم؛ اولي، صفر و يك است. يعني يك شيء يا به طور كامل در كوله‌پشتي قرار مي‌گيرد يا اصلا قرار نمي‌گيرد.
روش بعدي، روش كسري است كه مي‌توان بخشي از يك شيء را در كيسه قرار داد. مثلا مي‌توان دوسوم يك شيء را در كوله‌پشتي قرار داد.
هر دو حالت را توضيح خواهيم داد. بسيار خب فرض كنيد داريم:
S={item1,item2,item3,…,itemN}
Pitemi
Witemi
W
مجموعه S اشياي موجود را نشان مي‌دهد و دزد مي‌تواند آنها را انتخاب بكند و مقدار Pitem ارزش يك شيء و Witem وزن آن شيء است و W وزني است كه كوله‌پشتي مي‌تواند تحمل بكند.
اول روش صفر و يك را توضيح مي‌دهيم.
اولين استراتژي اين است كه بياييم تمام زير مجموعه‌هاي موجود از S را به دست بياوريم و سپس از بين آنها زير مجموعه‌اي را انتخاب كنيم كه داراي بيشترين ارزش باشد و وزن اشياي آن بيشتر از وزن كوله‌پشتي نباشد. آيا اين روش درست است؟
جواب قطعا خير است. مي‌دانيم‌تعدادزيرمجموعه‌هاي يك مجموعه n عضوي برابر 2 به توان n است، همان‌طور كه مشخص است اين راه براي مجموعه‌هاي بزرگ جوابگو نيست. اما راه‌حل چيست؟
يك راه اين است كه اشيا را به ترتيب وزن مرتب كنيم و سپس بيشترين‌ها را در كوله‌پشتي قرار دهيم. اين روش نيز منطقي نيست.
فرض كنيد يك وسيله داراي ارزش بيشتري است ولي وزن آن كمتر از بقيه است يا بعكس. نتيجه حاصل الزاما نتيجه بهينه مساله نيست.
راه‌حل ديگري كه ممكن است مطرح شود مثل همين راه بالاست، يعني به جاي اين‌كه بر اساس وزن مرتب كنيم بر حسب ارزش مرتب كنيم، اما نتيجه حاصل از اين روش نيز مانند روش بالا بهينه نيست. به‌خاطر اين‌كه ممكن است اشياي داراي ارزش بيشتر، وزن بيشتري داشته باشند و اگر در كوله‌پشتي قرار بگيرند الزاما نتيجه بهينه به
دست نمي‌آيد. چون ممكن است ارزش چند شيء سبك‌تر روي هم بيشتر از ارزش يك شيء بزرگ باشد. پس هميشه جواب بهينه را نمي‌دهد.
راه‌حل ديگري وجود دارد؟ روش بالا احتمالا شما را به اين راه‌حل نزديك كرده است. اين راه‌حل قصد دارد نارسايي روش‌هاي بالا را حل كند، اين روش مي‌گويد بهتر است اشيا بر اساس يك نسبت مشخص كه حاصل از نسبت ارزش به وزن آنهاست، در كوله‌پشتي قرار بگيرند با اين روش مشكلاتي كه در بالا گفته شد، به وجود نمي‌آيد به دليل اين كه شما يك نسبت داريد و اشيا بر حسب نسبت ارزش به وزن در كوله‌پشتي قرار مي‌گيرند پس اگر يك شيء ارزش بيشتري داشت و وزن كمتر، شانس بيشتري براي قرار گرفتن در كوله‌پشتي دارد.
بسيار خب در اولين مرحله نسبت ارزش به وزن را براي همه اشيا به دست مي‌آوريم سپس آنها را مرتب مي‌كنيم و اشيايي كه داراي نسبت بيشتر هستند ابتدا در كوله‌پشتي قرار مي‌گيرند تا زماني كه وزن اشياي موجود در كوله‌پشتي از W بيشتر نشود.
يك مثال مطرح مي‌كنيم كه در فهم بهتر اين موضوع به ما كمك مي‌كند، فرض كنيد داريم:
P1=5,W1=50
P2=10,W2=60
P3=20,W2=140
W=30
سپس نسبت ارزش به وزن را حساب مي‌كنيم:
Q=10
Q=6
Q=7
اگر اشيا را بر حسب اين نسبت در كوله‌پشتي قرار دهيم، ارزش كل اشياي موجود در كوله‌پشتي برابر 190مي‌شود، اما اگر آنها را بر اساس وزن قرار دهيم، ارزش كوله‌پشتي برابر 200 مي‌شود!
شايد شما هم تعجب كنيد كه چرا روش آخر نتيجه بهينه را به دست نمي‌آورد؟
اين خاصيت تمامي الگوريتم‌هاي حريصانه است كه هميشه اين نتيجه را به دست نمي‌آورند و براي بعضي مسائل نتيجه مي‌دهند پس هميشه نمي‌توان به آنها اطمينان كرد كه جواب بهينه بدهد.
اما روش كسري، در اين روش شما مي‌توانيد بخشي از اشيا را درون كوله‌پشتي خود قرار دهيد، مثلا دوسوم يك شيء را در كوله‌پشتي بگذاريد.
اين هم مثل همان روش نسبت ارزش به وزن است، اما در آخر اگر مجموع ارزش اشياي موجود در كوله‌پشتي از وزن كوله‌پشتي كمتر بود و اين وزن كمتر از وزن يك شيء بود، مي‌توان بخشي از شيء را در كوله‌پشتي قرار داد. بگذاريد با مثال توضيح دهيم:
در مثال بالا اشيا را بر حسب نسبت ارزش به وزن در كوله‌پشتي قرار داديم، پس ابتدا P1 سپس P3 مجموع ارزش آنها برابر 190 است و هنوز مي‌توان يك شيء با وزن 5 در كوله قرار داد، اما شيء P2 وزنش برابر 10 است! اين روش مي‌گويد كه مي‌توان نصف شيء P2 را در كوله‌پشتي قرار داد كه ارزش آن برابر 30 است. در نتيجه ارزش اشياي موجود در كوله‌پشتي برابر 220 مي‌شود و اشيايي كه در كوله‌پشتي‌اند به صورت زير هستند:
P1+P3+1/2P2
همان طور كه ديديد اين روش نتيجه بهينه‌تري نسبت به روش‌هاي قبلي داد.آيا اين روش نيز مثال نقضي دارد كه ثابت شود هميشه نتيجه بهينه نيست؟ اين مورد به عهده خواننده گذاشته مي شود.
امير بهاالدين سبط الشيخ
