مسئله کوله‌پشتی
مسئله کوله‌پشتی که با نام‌های Knapsack یا Rucksack مطرح می‌شود مسئله‌ای در بهینه‌سازی ترکیبیاتی است. فرض کنید مجموعه‌ای از اشیا که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به‌طوری‌که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آن‌ها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله‌پشتی‌ای با اندازهٔ محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند.
معمولاً در با محدودیت‌های مالی، با این مسئله روبرو هستیم. همچنین مسائلی از این قبیل در ترکیبیات، نظریه پیچیدگی محاسباتی، رمزنگاری و ریاضیات کاربردی به چشم می‌خورد.
نسخهٔ مسئله تصمیم برای مسئلهٔ کوله‌پشتی، این سؤال است: «آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر یا مساوی W قابل دستیابی است؟»
فرض کنید که جهانگردی می‌خواهدکوله‌پشتی خود را با انتخاب حالت‌های ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می‌سازند پر کند. این مسئله می‌تواند با شماره‌گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی (Binary) (j = ۱٬۲٬۳…n) به صورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می‌آورد و وزن آن و c اندازه کوله‌پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است که محدودیت را برآورده کند. بطوری‌که تابع هدف، بیشترین مقدار خود را بگیرد به عنوان نمونه‌ای از مسائلی که می‌توانند به صورت مسئله کوله‌پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه‌گذاری همه یا قسمتی ازسرمایه‌تان باشید. اگر مبلغی که برای سرمایه‌گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه‌گذاری ممکن باشد، اجازه دهیدکه سود حاصل از سرمایه‌گذاری j ام و مقدار دلارهایی باشد که آن سرمایه‌گذاری لازم دارد. بدین ترتیب جواب بهینه مسئله کوله‌پشتی که تعریف کردیم به ما این امکان را می‌دهدکه بهترین حالت ممکن را از بین حالت‌های گوناگون سرمایه‌گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه نخست، توجه ما را به خود جلب می‌کند عبارت از برنامه‌نویسی برای رایانه به منظور امتحان کردن همه بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می‌کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است. بطوری‌که یک رایانه فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = ۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = ۶۱ و ده‌ها سده برای n = ۶۵ والی آخر. با این وجود با استفاده از الگوریتم‌هایی خاص می‌توان در بسیاری موارد مسئله‌ای با n = ۱۰۰ ۰۰۰ را در عرض چند ثانیه روی یک رایانه کوچک حل کرد.
فرض کنید formula_1 جسم داریم که از formula_2 تا formula_1 شماره‌گذاری شده‌اند. جسم formula_4 ام ارزشی معادل formula_5و وزنی برابر با formula_6 دارد. معمولاً فرض می‌شود که وزن‌ها و ارزش‌ها نامنفی‌اند. برای ساده‌تر شدن نمایش، بدون کم شدن از کلیت مسئله می‌توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده‌اند. بیشترین وزنی که می‌توان در کوله‌پشتی حمل کرد،formula_7 است.
شناخته‌شده‌ترین نوع از این مسئله مسئلهٔ کوله‌پشتی ۰ و ۱ است. یعنی تعداد از هر شی، یا ۰ است (آن شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود). مسئلهٔ کوله‌پشتی ۰ و ۱ را می‌توان به این صورت، به زبان ریاضی بیان کرد:
مسئلهٔ کوله‌پشتی کران‌دار نسخهٔ دیگری از این سؤال است که در آن تعداد اشیا (formula_10) عددی صحیح و نامنفی و حداکثر برابر باformula_11 است. به بیان ریاضی:
مسئلهٔ کوله‌پشتی بیکران هیچ محدودیتی برای تعداد اشیا ندارد. یعنی از هر شی، به هر تعداد دلخواهی می‌توان انتخاب کرد. نسخه‌ای از این سؤال که بیش از همه مورد توجه قرار می‌گیرد، دارای ویژگی‌های زیر است:دقت کنید که در این مورد خاص، این مسئله هم ارز است با: " مجموعه‌ای از اعداد صحیح نا منفی داده شده‌است. آیا زیر مجموعه‌ای از آن وجود دارد که جمع اعضایش دقیقاً formula_7 شود؟" و چنانچه وزن‌های منفی هم قابل قبول باشند، و formula_7 برابر با formula_17 در نظر گرفته شود، مسئله عبارت است از: " مجموعه‌ای از اعداد صحیح داده شده‌است. آیا زیر مجموعه‌ای غیر تهی از آن هست که جمع اعضایش formula_17 شود؟" این مسئله خاص، مسئله جمع زیرمجموعه‌ها نامیده می‌شود. در رمزنگاری، هر گاه از مسئله کوله‌پشتی نام برده می‌شود، منظور مسئله جمع زیرمجموعه‌ها است.
چنانچه چند کوله‌پشتی داشته باشیم، مسئله تبدیل به سؤال می‌شود.
در این روش (knapsack (int n,int W برابر با حل مسئله در نظر گرفته می‌شود که از میان formula_1 شی با محدودیت ظرفیتی formula_7 تعدادی شی انتخاب می‌کنیم. اگر formula_21 اشیا بهینهٔ مد نظر باشد داریم:
۱. اگر formula_22 تابع به صورت (knapsack(int formula_23,int formula_7 صدا زده می‌شود.
۲. اگر formula_25 تابع به صورت (knapsack(int formula_23,int formula_27صدا زده می‌شود.
حال اگر formula_28 را برابر با ارزش راه حل بهینهٔ مسئله در نظر بگیریم داریم:
formula_29 همچنین به‌طور مشابه برای حالت دوم داریم: formula_30 using namespace std; void knapsack(int n,int W); int n,i,w,W; int weight[50],v[50]; int C[50][50]; void main() knapsack(n,W);
void knapsack(int n,int W)
for(i = 1; i <= n; i++){ for(i=1;i<=n;i++) cout«C[i][w]; //return C[i][w];
از دید علوم رایانه، مسئلهٔ کوله‌پشتی شایان توجه است زیرا:
مسئله جمع زیر مجموعه‌ها که نسخه‌ای از مسئلهٔ کلی کوله‌پشتی است، به عنوان یکی از ۲۱ مسئله ان‌پی-کامل کارپ مطرح است.
تلاش‌هایی برای استفاده از مسئلهٔ جمع زیر مجموعه‌ها به عنوان اصل در سیستم‌های رمزنگاری کلید عمومی، مانند سیستم رمزنگاری کوله‌پشتی مرکل-هلمن انجام شد. در این روش‌ها، معمولاً از گروه‌هایی به جز اعداد صحیح استفاده می‌شد. Merkle-Hellman و الگوریتم‌های مشابه دیگر بعداً با شکست روبرو شدند زیرا مسائل خاصی که تولید می‌کردند در قابل حل بودند.
در بسیاری از پژوهش‌ها تلاش می‌شود نمونه‌های سخت مسئلهٔ کوله‌پشتی یافت شود. به بیان دیگر، چه ویژگی‌هایی از نمونه‌های مسئلهٔ کوله‌پشتی، باعث می‌شود در زمانی معقولتر نسبت به آنچه در صورت کلی NP-completeِ مطرح است، حل شوند. الگوریتم‌های زیادی بر پایه برنامه‌نویسی پویا، الگوریتم تقسیم و حل یا ترکیبی از هر دو روش برای این مسئله وجود دارند.
اگر همه وزن‌ها (formula_31) اعداد صحیح نامنفی باشند مسئلهٔ کوله‌پشتی در زمانی شبه چندجمله‌ای با استفاده از برنامه‌نویسی پویا قابل حل است.
برای سادگی فرض کنید همه وزن‌ها اکیداً مثبت اند (formula_32). می‌خواهیم جمع ارزش کالاهای انتخاب شده را بیشینه کنیم با این فرض که مجموع وزن آن‌ها حداکثرformula_33 شود. حال برای هر formula_34، مقدار formula_35 را بیشترین ارزش قابل دستیابی تعریف کنید به‌طوری‌که جمع وزن اشیا انتخاب شده حداکثر formula_36 شود. بدیهی است که formula_37 پاسخ مورد نظر است.
دقت کنید که formula_35 ویژگی‌های زیر را دارد:
بیشترین ارزش قابل دستیابی از مجموعهٔ تهی، ۰ است. برای محاسبهٔ هر کدام از formula_42ها، باید formula_1 شی را بررسی کرد. همچنین آرایهٔ formula_7، formula_45 عنصر دارد؛ بنابراین زمان اجرای این الگوریتم formula_46 است. بدیهی است با تقسیم کردن formula_47 بر بزرگترین مقسوم علیه مشترک می‌توان زمان اجرای الگوریتم را بهینه کرد.
پیچیدگی زمانی formula_46 تناقضی با NP-complete بودن مسئلهٔ کوله‌پشتی ندارد. زیرا formula_7 برخلاف formula_1، برحسب ورودی چندجمله‌ای نیست. طول formula_7 ِ ورودی، متناسب با تعداد بیت‌های لازم برای نمایش formula_7، یعنی formula_53 است، نه خود formula_54.
روش مشابهی با استفاده از برنامه‌سازی پویا برای حل مسئله کوله‌پشتی ۰ و ۱ با وجود دارد. مانند بالا، فرض کنید formula_47ها اعداد صحیح اکیداً مثبتی هستند. formula_56 را بیشترین ارزش قابل دستیابی، با استفاده از اشیای ۱ تا formula_57 با حداکثر وزن formula_36 تعریف کنید.
formula_56 را می‌توان به‌طور بازگشتی، مطابق زیر تعریف کرد:
پاسخ با محاسبهٔ formula_66 بدست می‌آید. برای کارآمد شدن راه حل، می‌توان از جدولی برای نگهداری نتایج محاسبات قبلی استفاده کرد؛ بنابراین پیچیدگی زمانی آن formula_46 و حافظه formula_46 خواهد شد. همچنین می‌توان حجم حافظه را به formula_69 کاهش داد. به این ترتیب که آرایهٔ یک بعدیformula_35، ارزش بهینه تاکنون را نشان می‌دهد. از formula_71 شروع کرده، آرایه را پر می‌کنیم. سپس با حرکت بر روی formula_57، مقدار formula_35 را با افزدون یک شی جدید به انتخاب‌ها، به روز آوری می‌کنیم.
الگوریتم دیگری برای مسئله کوله‌پشتی ۰ و ۱ در سال ۱۹۷۴ ارائه شد که گاهی «رویارویی در میانه» نیز نامیده می‌شود. این الگوریتم نسبت به تعداد اشیا نمایی است. (این اسم، از الگوریتمی مشابه در رمزنگاری نشات گرفته‌است). هنگامی که formula_7 نسبت به formula_1 بسیار بزرگتر باشد (یعنیformula_7 از formula_77 هم بزرگتر باشد) این الگوریتم نسبت به روش پویا از نظر زمانی بهینه تر است. برای نمونه فرض کنید formula_6ها نامنفی باشند اما صحیح نباشند. در اینجا نیز می‌توان از روش پویا استفاده کرد: اگر عددها formula_79 رقم بعد از اعشار داشته باشند کافی است آن‌ها را در formula_80 ضرب و سپس رند کرد (با استفاده از محاسبات ممیز ثابت). روش پویا با این تغییرات، از مرتبهٔ زمانی formula_81 و حافظهٔ formula_82 خواهد بود.
الگوریتم «رویارویی در میانه» به صورت زیر است:
این الگوریتم از مرتبهٔ حافظهٔ formula_92 است و با پیاده‌سازی بهینه گام ۳، از مرتبهٔ زمانی formula_93 می‌شود. (برای نمونه با مرتب کردن زیرمجموعه‌های formula_94 بر حسب وزن، چشم پوشی از زیر مجموعه‌هایی از formula_94 که وزنی بیشتر از سایر زیر مجموعه‌ها با ارزش بزرگتر/مساوی دارند و استفاده از جستجوی دودویی برای یافتن بهترین تطابق). مانند روش رویارویی در میانه در رمز نگاری، استفاده از این الگوریتم با هزینه کردن حافظه (مرتبهٔ نمایی به جای مقدار ثابت) باعث بهینه شدن زمان اجرا می‌شود. می‌دانیم چنانچه بخواهیم همه زیر مجموعه‌های {۱...n} را به روش brute force بررسی کنیم، مرتبهٔ زمانی formula_96 خواهد شد اما با این الگوریتم آن را بهینه کردیم. جرج دانتزیگ الگوریتمی تقریبی از نوع حریصانه برای حل مسئله کوله‌پشتی بیکران ارائه داد.
به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می‌کند (formula_97) سپس از شی شماره ۱ شروع می‌کند. بیشترین تعداد ممکن از آن را در کوله‌پشتی قرار می‌دهد، تا زمانی که دیگر جای خالی‌ای برای آن نوع باقی نماند. آنگاه سراغ شی بعدی می‌رود. (دقت کنید که در این نسخه از سؤال، محدودیتی برای تعداد اشیا نداریم) اگر formula_45 بیشینه ارزش اشیایی باشد که در کوله‌پشتی جا می‌شوند، این الگوریتم حداقل به مقدار formula_99 دست می‌یابد. اما اگر تعداد مجاز از هر شی محدود باشد، ممکن است خروجی این الگوریتم از پاسخ بهینه بسیار دور باشد.
در حل مسئلهٔ کوله‌پشتی بیکران، با کنار گذاشتن اشیایی که هیچوقت مورد استفاده قرار نمی‌گیرند، می‌توان مسئله را ساده‌تر کرد. برای نمونه، فرض کنید برای شی‌ای مانند "i"، می‌توان زیر مجموعه از اشیا به نام "J" یافت طوری‌که ارزش مجموع آن‌ها بزرگتر از ارزش "i" و وزن مجموع آن‌ها کمتر از وزن "i" باشد؛ بنابراین، "i" نمی‌تواند در جواب بهینه بیاید. در این هنگام مجموعهٔ "J" را پوشاننده ی "i" می‌گوییم. (توجه کنید این استدلال برای مسئلهٔ کوله‌پشتی کراندار نمی‌تواند مورد استفاده قرار گیرد. زیرا ممکن است قبلاً از اشیا سازندهٔ مجموعهٔ "J" استفاده کرده باشیم و تمام شده باشند)
پیدا کردن روابط پوشانندگی به ما کمک می‌کند تا حجم فضای جستجو را به اندازه چشمگیری کاهش دهیم. انواع گوناگون از روابط پوشانندگی وجود دارند که همگی در نامساوی زیر صدق می‌کنند:
formula_100، and formula_101 for some formula_102
که: formula_103 و formula_104. و formula_105 تعداد انتخاب‌های شی نوع "j" را نشان می‌دهد. (دقت کنید این "j"ها، اعضای مجموعهٔ "J" هستند)
شی formula_106 ام به‌طور انتخابی توسط formula_107 پوشانده شده، اگر جمع وزن شماری از اعضای مجموعهٔ formula_107، کمتر از formula_109 باشد و جمع ارزش آن‌ها بیشتر از formula_110. به بیان ریاضی:
formula_111 و formula_112 درصورتی که formula_102 که formula_114.
بررسی این نوع پوشانندگی، از لحاظ پیچیدگی محاسباتی چندان ساده نیست، بنابراین از بهترین روش‌ها، راه حل پویاست. در واقع این مسئله، یک مسئله کوله‌پشتی، اما با پارامترهای کوچکتر، مطابق زیر است:
formula_115، formula_116 و اشیا محدود به مجموعهٔ formula_117 هستند.
نماد ریاضی پوشانندگی انتخابی به صورت formula_118 است.
اگر شماری از اشیا نوع formula_106 توسط formula_107 پوشانده شوند شی formula_106 ام، تا اندازه‌ای توسط formula_107 پوشانده می‌شود. به بیان ریاضی:
formula_100 و formula_101 در صورتی که formula_102 و formula_126.
این نوع پوشانندگی، نمایش کلی تری از پوشانندگی انتخابی نیست که برای نخستین‌بار در معرفی شد و در الگوریتم EDUK مورد استفاده قرار گرفت. کوچکترین formula_127 ممکن، حد formula_57 نامیده می‌شود. به بیان ریاضی: formula_129. در این هنگام، پاسخ بهینه حداکثر می‌تواند به تعداد formula_130 شی، از نوع formula_57 را شامل شود.
شی formula_106، به‌طور چندگانه توسط شی formula_133 پوشانده شده، اگر formula_106 توسط شماری از شی نوع formula_133 پوشانده شود. (یعنی شی formula_106، فقط توسط تعدادی شی از نوع formula_133 پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد). به بیان ریاضی:
formula_138 و formula_139 برای formula_140
که formula_141.
این پوشانندگی می‌تواند برای بهینه کردن پروسهٔ حل مورد استفاده قرار گیرد، زیرا تشخیص روابط پوشانندگی از این نوع، به محاسبات زیادی نیاز ندارد و نسبتاً ساده است.
نماد ریاضی پوشانندگی انتخابی به صورت formula_142 است.
فرض کنیم formula_143 بهترین شی باشد یعنی برای همه formula_106ها formula_145. formula_143 شی‌ای با بیشترین چگالی است.
شی formula_106 ام، به‌طور ماژولار توسط شی formula_133 پوشانده شده، اگر توسط formula_133 و تعدادی شی از نوع formula_143 پوشانده شود. (یعنی شی formula_106، فقط توسط formula_133 و تعدادی شی از نوع formula_143 پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد) به بیان ریاضی:
formula_154 و formula_155
که formula_156.
نماد ریاضی پوشانندگی ماژولار به صورت formula_157 است.
void Greedy Knapsack(w,n) //W is the knapsack and the n objects sort (p,w)//Pi/Wi>=Pi+1/Wi+1 for(i=0;iمسئله بهینه‌سازی است، ما رد بهترین مجموعه کنونی کالاها و مجموع ارزش آن‌ها را نگه می‌داریم که اینکار توسط ارائه bestset و و یک متغیر maxprofit انجام می‌شود. این مسئله را برای یافتن نخستین جواب بهینه مطرح می‌کنیم
مسئله:n کالا داریم که هر کدام از آن‌ها دارای ارزشی و وزنی دارند. ارزش‌ها و وزن‌ها، اعدادی صحیح و مثبت هستند. مجموعه‌ای از کالاها با حداکثر مجموع ارزش را طوری تعیین کنید که مجموع اوزان آن‌ها بیش از عدد صحیح مثبت w نشود
ورودی:اعداد صحیح مثبت nوw,ارایه‌های wوpکه از ۱ تاn شاخص دهی شده و هر یک شامل اعداد صحیح و مثبتی هستند که به ترتیب غیر نزولی بر اساس مقادیر [p[i]/w[i مرتب شده‌اند
خروجی:مقدار صحیح maxprofit که بیشترین ارزش است ارائه bestset که از ۱ تا n شاخص دهی شده و در مقادیر bestsetو "yes"است اگر کالای iام در مجموعه بهینه قرار داشته باشد در غیر اینصورت مقدار ان "no" می‌باشد
طبق قرار دادn,w,p,W ,numbest , bestset , include , maxprofit ورودی‌های روتین نیستند. اگر این متغیرهای را به صورت سراسری تعریف می‌کردیم، شبه کد زیر بیشترین ارزش و مجموعه دارای این ارزش را تولید می‌کرد:
مسئلهٔ کوله پشتی می‌تواند در تصمیم‌گیری‌هایی که در دنیای واقعی با آن‌ها روبرو هستیم، مورد استفاده قرار گیرد. مانند بریدن کالا به‌طوری‌که کمترین مقدار به هدر رود، انتخاب سرمایه‌گذاری‌ها و سبد سهام، انتخاب دارایی‌ها برای و ساختن کلیدها برای .
یکی از کاربردهای اولیهٔ مسئلهٔ کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون‌دهنده در پاسخگویی به سؤالات حق انتخاب داشته باشد. چنانچه بارم بندی سؤالات همگن باشد، مسئله بسیار ساده خواهد شد. برای نمونه، اگر آزمون دارای ۱۲ سؤال، هر سؤال به ارزش ۱۰ نمره باشد، آزمون دهنده باید فقط ۱۰ سؤال را پاسخ دهد تا به بیشینه نمره ممکنِ ۱۰۰ برسد. اما برای آزمون‌هایی با بارم بندی نایکسان، مسئله کمی سخت‌تر می‌شود. Feuerman و Weiss سیستمی ارائه دادند که در آن دانش آموزان با آزمونی با بارم بندی ناهمگن، با جمع بارم ۱۲۵ روبرو هستند. از دانش آموزان خواسته می‌شود با توجه به توانایی‌های خود به سؤالات پاسخ دهند. در اینجا با مسئلهٔ کوله پشتی روبرو هستیم. چه زیر مجموعه‌هایی، جمع نمره‌ای برابر با ۱۰۰ خواهند داشت؟ برای هر دانش آموز، پاسخ‌گویی به کدام زیر مجموعه از سؤالات، نمرهٔ بیشتری را به ارمغان می‌آورد؟
صورت مسئله: دزدی قصد سرقت از مغازه‌ای را دارد و حداکثر وزن w از اجناس را که می‌تواند بدزد در این مغازه n نوع جنس وجود دارد. اگر وزن جنس iام wi و قیمت آن vi باشد بیشینه سودی که بدست می‌آورد چقدر است؟
این مسئله به دو صورت تعریف می‌شود:
در حالت صفر و یک مسئله به این صورت تعریف می‌شود که دزد یا یک جنس را برمی‌دارد یا برنمی‌دارد و حق برداشتن تکه‌ای از یک جنس را ندارد. برای این مسئله راه حل حریصانه‌ای وجود ندارد و به ارائه یک راه حل پویا خواهیم پرداخت.
ایده حل این مسئله در حالت پویا یه ابن صورت هست که دزد یا جنس iام را برمی‌دارد یا برنمی‌دارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه می‌شود و از مسیری که جواب بیشینه را داده پیش خواهیم رفت. به عبارتی: کد c[i,w] = c[i-1, w] شبه کد Dynamic-0-1-knapsack (v, w, n, W) در این حالت از مسئه دزد می‌تواند قسمتی از یک جنس را بردارد و مثل حالت قبل ۰ و ۱ی نمی‌باشد. برای این مسئله راه حال حریصانه وجود داره و به این شکل هست که دزد تا می‌تواند جنس پرارزش تر را برداشته و درصورتی که نتوانست بیشترین کسر ممکن آن را برمی‌دارد.
مسئلهٔ کوله پشتی بیش از یک سده مورد مطالعه قرار گرفته و نخستین بررسی در سال ۱۸۹۷ انجام گرفته‌است. هر چند نخستین داده‌های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (۱۸۸۴–۱۹۵۶) باز می‌گردد چیزی با عنوان مسئلهٔ کوله پشتی قبلاً در میان عامهٔ مردم وجود داشته‌است.
مسئلهٔ کوله پشتی درجه دوم، نخستین‌بار توسط Hammer, Gallo و Simeone در سال ۱۹۶۰ مطرح شد.
در سال ۱۹۸۸ پژوهشی از دانشگاه استونی بروک بر روی مجموعه‌ای از الگوریتم‌ها نشان داد که از میان ۷۵ مسئلهٔ الگوریتمی، مسئلهٔ کوله پشتی ۱۸امین مسئلهٔ سرشناس و ۴امین مسئلهٔ پرکاربرد پس از درخت کی‌دی، درخت پسوندی، و مسئله بین پکینگ است.