مسئله کوله پشتی چیست؟ الگوریتم، انواع و تغییرات

چکیده مقاله :
مسئله کوله پشتی (Knapsack Problem) نمونه ای از مسئله بهینه سازی ترکیبی است. این مسئله معمولاً به عنوان “مشکل کوله پشتی” نیز شناخته می شود. نام مسئله از مسئله بیشینه سازی به صورت زیر تعریف می شود: با توجه به یک کوله با حداکثر ظرفیت وزن W و مجموعه‌ای از اقلام که هر کدام دارای وزن و مقدار مرتبط با آن هستند. تعداد هر اقلام را به گونه ای تعیین کنید که وزن کل کمتر از ظرفیت باشد و ارزش کل به حداکثر برسد.

مسئله کوله پشتی چیست؟

مسئله کوله پشتی یک مسئله معروف برنامه نویسی پویا است که در دسته بهینه سازی قرار می گیرد.

• برنامه نویسی

نام خود را از سناریویی گرفته است که در آن، با توجه به مجموعه‌ای از آیتم‌ها با وزن‌های خاص و مقادیر اختصاص داده شده، هدف این است که مقدار را در یک کوله پشتی به حداکثر برسانیم در حالی که در محدودیت وزن باقی می‌مانیم.

هر مورد فقط یک بار قابل انتخاب است، زیرا ما تعداد زیادی از هیچ موردی نداریم.

در مثال زیر وزن لانه زنبوری های مختلف و مقادیر مربوط به آنها ارائه شده است. هدف، به حداکثر رساندن ارزش عسلی است که می تواند در کوله پشتی خرس قرار گیرد.

درنتیجه مسئله کوله پشتی یک مسئله بهینه سازی است که برای نشان دادن مسئله و راه حل استفاده می شود. این نام خود را از سناریویی گرفته است که در آن تعداد مواردی که می توان در یک کوله پشتی با اندازه ثابت قرار داد محدود می شود. با توجه به مجموعه‌ای از اقلام با وزن‌ها و مقادیر مشخص، هدف این است که با توجه به محدودیت وزن کوله‌پشتی، تا حد امکان ارزش بیشتری را به کوله پشتی وارد کنید.

• مشاوره برنامه نویسی

انواع مسئله کوله پشتی

Knapsack Problem را می توان به انواع زیر طبقه بندی کرد:

• مسئله کوله پشتی کسری Fractional Knapsack Problem
• مسئله 0/1 کوله پشتی 0/1Knapsack Problem 
• مسئله کوله پشتی محدود Bounded Knapsack Problem
• مسئله کوله پشتی نامحدود Unbounded Knapsack Problem

1. مسئله کوله پشتی کسری

همانطورکه گفته شد، Knapsack Problem بیان می کند که – با توجه به مجموعه ای از اقلام، وزن نگهدارنده و ارزش سود، باید زیرمجموعه اقلامی را که باید در یک کوله پشتی اضافه شوند تعیین کرد به طوری که وزن کل اقلام نباید از حد کوله پشتی تجاوز کند. ارزش کل سود آن حداکثر است.

مسئله کوله پشتی کسری را می توان به صورت زیر تعریف کرد:

با توجه به وزن و مقادیر N آیتم، این اقلام را در یک کوله پشتی با ظرفیت W قرار دهید تا حداکثر مقدار کل در کوله پشتی به دست آید. در کوله پشتی کسری، می توانیم آیتم ها را برای به حداکثر رساندن ارزش کل کوله پشتی بشکنیم.

• تحلیل آماری

برای اینکه این مسئله کمی ساده تر توضیح داده شود، آزمونی با 12 سؤال، هر کدام 10 نمره، در نظر بگیرید، که از بین آنها فقط باید 10 تا را امتحان کرد تا حداکثر نمره 100 را به دست آورد. آزمون شونده اکنون باید بیشترین سود را محاسبه کند – سؤالی که او دارد. اعتماد به نفس – برای دستیابی به حداکثر نمره. با این حال، او نمی تواند تمام 12 سوال را امتحان کند زیرا هیچ نمره اضافی برای آن پاسخ های تلاش شده اعطا نخواهد شد. این ابتدایی ترین کاربرد در دنیای واقعی Knapsack Problem است.

2. مسئله 0/1 کوله پشتی

مسئله 0/1 Knapsack را می توان به صورت زیر تعریف کرد:

به ما N آیتم داده می شود که هر آیتم مقداری وزن (wi) و مقدار (vi) مرتبط با آن دارد. همچنین یک کیسه با ظرفیت W به ما داده می شود. هدف این است که اقلام را به گونه ای در کیسه قرار دهیم که مجموع مقادیر مرتبط با آنها حداکثر ممکن باشد.

توجه داشته باشید که در اینجا می‌توانیم یک مورد را به طور کامل در کیف قرار دهیم یا اصلاً نمی‌توانیم آن را قرار دهیم.

از نظر ریاضی می توان مسئله را به صورت زیر بیان کرد:

3. مسئله کوله پشتی محدود

مسئله Bounded Knapsack را می توان به صورت زیر تعریف کرد:

با توجه به N مورد، هر آیتم دارای وزن معین wi و مقدار vi است، وظیفه این است که با انتخاب حداکثر K آیتم با جمع حداکثر وزن W، مقدار را به حداکثر برسانیم.

از نظر ریاضی می توان مسئله را به صورت زیر بیان کرد:

4. مسئله کوله پشتی نامحدود

مسئله Unbounded Knapsack را می توان به صورت زیر تعریف کرد:

با توجه به وزن کوله پشتی W و مجموعه ای از N آیتم با مقدار مشخص vi و وزن wi، باید حداکثر مقداری را که می تواند دقیقاً این مقدار را تشکیل دهد محاسبه کنیم. این با مسئله 0/1 Knapsack متفاوت است، در اینجا ما مجاز به استفاده از تعداد نامحدودی از نمونه های یک آیتم هستیم.

از نظر ریاضی می توان مسئله را به صورت زیر بیان کرد:

الگوریتم کوله پشتی

وزن (Wi) و مقادیر سود (Pi) اقلامی که باید در کوله پشتی اضافه شوند به عنوان ورودی برای الگوریتم کوله پشتی کسری در نظر گرفته شده و زیرمجموعه اقلام اضافه شده در کوله پشتی بدون تجاوز از حد و با حداکثر سود به عنوان خروجی به دست می آید.

الگوریتم

• همه موارد را با وزن و سود ذکر شده به ترتیب در نظر بگیرید.
• Pi/Wi همه موارد را محاسبه کنید و موارد را بر اساس مقادیر Pi/Wi آنها به ترتیب نزولی مرتب کنید.
• بدون تجاوز از حد، موارد را به کوله پشتی اضافه کنید.
• اگر کوله پشتی بازهم بتواند مقداری وزن را ذخیره کند، اما وزن سایر موارد از حد مجاز فراتر رود، می توان قسمت کسری دفعه بعدی را اضافه کرد.
• از این رو، نام مسئله کوله پشتی کسری را به آن می دهیم.

کوله پشتی کسری یک نوع از Knapsack Problem می باشد که بقیه انواع آن را در بخش های قبل توضیح دادیم.

• الگوریتم گرگ خاکستری

• الگوریتم زنبور عسل

تغییرات مسئله کوله پشتی

چندین تغییر ممکن برای مشکل کوله پشتی وجود دارد. برخی از تغییرات شناخته شده در زیر ارائه شده است:

1. مسئله کوله پشتی چند هدفه

در این تنوع، هدف از پر کردن کوله پشتی تغییر می کند. به جای به حداکثر رساندن تنها ارزش، چندین هدف دیگر می تواند وجود داشته باشد.

به عنوان مثال: در نظر بگیرید که در حال برگزاری یک نمایش موسیقی در سالنی با ظرفیت 10000 نفر هستید. شما در حال برگزاری یک نمایش هستید و تعداد مخاطب بستگی به محبوبیت خواننده دارد. همچنین هر چه خواننده محبوب تر باشد، دستمزد آن بیشتر می شود. شما می خواهید سود را به حداکثر برسانید و مبلغی را که برای خواننده خرج می شود به حداقل برسانید و همچنین می خواهید تا جایی که ممکن است خواننده بیشتری بیاورید.

2. مسئله کوله پشتی چند بعدی

در این تغییر مسئله، وزن هر آیتم i با بردار بعدی M {wi1, wi2, . . . wiM} و به طور مشابه، ظرفیت کوله نیز یک بردار بعدی M است {W1, W2, . . . ، WM}.

3. مسئله کوله پشتی چندگانه

این تغییر Knapsack Problem شبیه به الگوریتم Bin Packing است. تفاوت در هر دو مشکل اینجاست که ما می‌توانیم زیرمجموعه‌ای از آیتم‌ها را انتخاب کنیم، در حالی که در مسئله Bin Packing، باید همه موارد را در هر یک از سطل‌ها بسته بندی کنیم. ایده این است که چند کوله پشتی وجود دارد که به نظر می رسد ظرفیت اضافه کردن به کوله پشتی اولیه باشد، اما اصلا شبیه آن نیست.

4. مسئله کوله پشتی درجه دوم

این تغییر هدف دستیابی به حداکثر مقدار یک تابع هدف درجه دوم است که در معرض محدودیت های ظرفیت باینری و خطی است.

5. مسئله کوله پشتی هندسی

در این تغییر، مجموعه ای از مستطیل ها با مقادیر مختلف و یک کوله پشتی مستطیلی وجود دارد. هدف این است که بیشترین ارزش ممکن را در کوله پشتی قرار دهید.

کاربردهای مسئله کوله پشتی

Knapsack Problem چندین برنامه کاربردی در زندگی واقعی دارد. در اینجا به برخی از آنها اشاره می شود:

• یکی از کاربردهای اولیه Knapsack Problem در ساخت و نمره گذاری امتحاناتی بود که در آن آزمون شوندگان حق انتخابی برای پاسخ به سؤالات دارند.
• مسئله جمع زیر مجموعه با استفاده از مفهوم مسئله کوله پشتی حل می شود.
• تغییرات هدف چندگانه Knapsack Problem اغلب برای مسائل بهینه سازی لجستیک حمل و نقل استفاده می شود.
• مسئله چند کوله پشتی اغلب در بسیاری از الگوریتم های بارگذاری و زمان بندی در تحقیقات عملیاتی استفاده می شود.