مسئله کوله پشتی که با عنوان های Knapsackیا Rucksackمطرح می شود، مسئله ای در بهینه سازی ترکیباتی است.
فرض کنید مجموعه ای از اشیا، که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به طوری که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آنها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله پشتی ای با اندازه ی محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند. روش انجام کار : از الگوریتمی تقریبی از نوع حریصانه برای حل مسئله کوله پشتی استفاده می کنیم. به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می کند ( ) سپس از شی شماره 1شروع می کند.بیشترین تعداد ممکن از آن را در کوله پشتی قرار می دهد، تا زمانی که دیگر جای خالی ای برای آن نوع باقی نماند. آنگاه سراغ شی بعدی میرود. ( دقت کنید که در این نسخه از سوال، محدودیتی برای تعداد اشیا نداریم) اگر بیشینه ارزش اشیایی باشد که در کوله پشتی جا می شوند، این الگوریتم حداقل به مقدار دست می یابد.اما اگر تعداد مجاز از هر شی محدود باشد، ممکن است خروجی این الگوریتم از پاسخ بهینه بسیار دور باشد. نتیجه نهایی : در حل مسئله ی کوله پشتی ، با کنار گذاشتن اشیایی که هیچوقت مورد استفاده قرار نمی گیرند، می توان مسئله را ساده تر کرد. برای مثال، فرض کنید برای شی ای مانند ،iمی توان زیر مجموعه از اشیا به نام Jیافت طوری که ارزش مجموع آنها بزرگتر از ارزش iو وزن مجموع آنها کمتر از وزن iباشد. بنابراین، iنمی تواند در جواب بهینه بیاید. در این هنگام مجموعه ی Jرا پوشاننده ی iمی گوییم . بدترین زمان اجرایی این الگوریتم ( O(n می باشد
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team