مسئله کوله پشتی که با عنوان های Knapsack یا Rucksack مطرح می شود، مسئله ای در بهینه سازی ترکیبیاتی است. فرض کنید مجموعه ای از اشیا، که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به طوری که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آنها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله پشتی ای با اندازه ی محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند. فرض کنید n جسم داریم که از 1 تا n شماره گذاری شده اند. جسم i ام ارزشی معادلvi و وزنی برابر با wi دارد. معمولا فرض می شود که وزن ها و ارزش ها نامنفی اند.
جهت مشاهده ادامه مطالب و دسترسی به کد این برنامه
لینک اصلی را کلیک نمایید.