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

مسئله کوله پشتی که با نام های Knapsack یا Rucksack مطرح می شود مسئله ای در بهینه سازی ترکیبیاتی است. فرض کنید مجموعه ای از اشیا که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به طوری که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آن ها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله پشتی ای با اندازهٔ محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند.
معمولاً در تخصیص منابع با محدودیت های مالی، با این مسئله روبرو هستیم. همچنین مسائلی از این قبیل در ترکیبیات، نظریه پیچیدگی محاسباتی، رمزنگاری و ریاضیات کاربردی به چشم می خورد.
نسخهٔ مسئله تصمیم برای مسئلهٔ کوله پشتی، این سؤال است: «آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر یا مساوی W قابل دستیابی است؟»
فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالت های ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی ( Binary ) ( j = ۱٬۲٬۳…n ) به صورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است که محدودیت را برآورده کند. بطوری که تابع هدف، بیشترین مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند به صورت مسئله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد. بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالت های گوناگون سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه نخست، توجه ما را به خود جلب می کند عبارت از برنامه نویسی برای رایانه به منظور امتحان کردن همه بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است. بطوری که یک رایانه فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = ۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = ۶۱ و ده ها سده برای n = ۶۵ والی آخر. با این وجود با استفاده از الگوریتم هایی خاص می توان در بسیاری موارد مسئله ای با n = ۱۰۰ ۰۰۰ را در عرض چند ثانیه روی یک رایانه کوچک حل کرد.