شریک دزد شوید!

یعنی به او بگوییم چه وسایلی را به ترتیب بردارد که علاوه بر ارزش بالایشان، حجم آنها طوری باشد که در کوله‌پشتی‌اش جا شوند.

در این روش 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

همان طور که دیدید این روش نتیجه بهینه‌تری نسبت به روش‌های قبلی داد.آیا این روش نیز مثال نقضی دارد که ثابت شود همیشه نتیجه بهینه نیست؟ این مورد به عهده خواننده گذاشته می شود.

امیر بهاالدین سبط الشیخ