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

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

فرض کنید ${\displaystyle n}$

شناخته‌شده‌ترین نوع از این مسئله مسئلهٔ کوله‌پشتی ۰ و ۱ است. یعنی تعداد از هر شی، یا ۰ است (آن شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود). مسئلهٔ کوله‌پشتی ۰ و ۱ را می‌توان به این صورت، به زبان ریاضی بیان کرد:

• مقدار ${\displaystyle \sum _{i=1}^n{v}_i{x}_i}$
  را بیشینه کنید.
• به‌طوری‌که ${\displaystyle \sum _{i=1}^n{w}_i{x}_i⩽W,x_i\in \{0,1\}}$

مسئلهٔ کوله‌پشتی کران‌دار نسخهٔ دیگری از این سؤال است که در آن تعداد اشیا (${\displaystyle x_i}$

• مقدار ${\displaystyle \sum _{i=1}^n{v}_i{x}_i}$
  را بیشینه کنید.
• به‌طوری که${\displaystyle \sum _{i=1}^n{w}_i{x}_i⩽W,x_i\in \{0,1,\dots ,c_i\}}$

مسئلهٔ کوله‌پشتی بیکران هیچ محدودیتی برای تعداد اشیا ندارد. یعنی از هر شی، به هر تعداد دلخواهی می‌توان انتخاب کرد. نسخه‌ای از این سؤال که بیش از همه مورد توجه قرار می‌گیرد، دارای ویژگی‌های زیر است:

• یک مسئله تصمیم است.
• مسئله ۰ و ۱ است.
• برای هر شی، وزن و ارزش آن برابرند. یعنی${\displaystyle w_i=v_i}$
  .

دقت کنید که در این مورد خاص، این مسئله هم ارز است با: " مجموعه‌ای از اعداد صحیح نا منفی داده شده‌است. آیا زیر مجموعه‌ای از آن وجود دارد که جمع اعضایش دقیقاً ${\displaystyle W}$

چنانچه چند کوله‌پشتی داشته باشیم، مسئله تبدیل به سؤال bin packing می‌شود.

شیوهٔ پیاده‌سازی الگوریتم

در این روش (knapsack (int n,int W برابر با حل مسئله در نظر گرفته می‌شود که از میان ${\displaystyle n}$

۱. اگر ${\displaystyle x_n=0}$

۲. اگر ${\displaystyle x_n=1}$

حال اگر ${\displaystyle C[n,W]}$

همچنین به‌طور مشابه برای حالت دوم داریم:

 
#include<iostream>
using namespace std;
#include<stdio.h>
void knapsack(int n,int W);
int n,i,w,W;
int weight[50],v[50];
int C[50][50];
void main()
{
 cout<<"Enter number of items";
 cin>>n;
 cout<<"Enter Capacity";
 cin>>W;
 cout<<"Enter weights";
 for(i=0;i<n;i++)
 {
  cin>>weight[i];
 }
 cout<<"Enter values";
        for(i=0;i<n;i++)
 {
  cin>>v[i];
 }
knapsack(n,W);
         
}

void knapsack(int n,int W)
{

for(i = 1; i <= n; i++){
        C[i][0] = 0;
 //cout<<C[i][0];
  }
for(i=1;i<=n;i++)
{
          for(w=0;w<=W;w++)
                  if(weight[i]<=w)                                                 //item can be put in knapsack
                         if(v[i]+C[i-1][w-weight[i]]>C[i-1][w])
                  C[i][w]=v[i]+C[i-1][w-weight[i]];
        else
                  C[i][w]=C[i-1][w];
                 else
                         C[i][w]=C[i-1][w];                      // w[i]>w
}
cout<<C[i][w];
//return C[i][w];
}

از دید علوم رایانه، مسئلهٔ کوله‌پشتی شایان توجه است زیرا:

• الگوریتمی با زمان اجرای شبه چندجمله‌ای با استفاده از برنامه‌نویسی پویا دارد.
• الگوریتمی تقریبی با زمان چندجمله‌ای دارد که از الگوریتم‌های با زمان شبه چندجمله‌ای به عنوان یک زیر-برنامه استفاده می‌کند.
• حل دقیق این سؤال، مسئله‌ای از نوع NP-complete است؛ بنابراین پیش‌بینی شده که راه حلی که هم درست و هم سریع باشد (با زمان اجرای چندجمله‌ای) برای هر ورودی دلخواه، ندارد.

مسئله جمع زیر مجموعه‌ها که نسخه‌ای از مسئلهٔ کلی کوله‌پشتی است، به عنوان یکی از ۲۱ مسئله ان‌پی-کامل کارپ مطرح است.

تلاش‌هایی برای استفاده از مسئلهٔ جمع زیر مجموعه‌ها به عنوان اصل در سیستم‌های رمزنگاری کلید عمومی، مانند سیستم رمزنگاری کوله‌پشتی مرکل-هلمن انجام شد. در این روش‌ها، معمولاً از گروه‌هایی به جز اعداد صحیح استفاده می‌شد. Merkle-Hellman و الگوریتم‌های مشابه دیگر بعداً با شکست روبرو شدند زیرا مسائل خاصی که تولید می‌کردند در زمان چندجمله‌ای قابل حل بودند.

در بسیاری از پژوهش‌ها تلاش می‌شود نمونه‌های سخت مسئلهٔ کوله‌پشتی یافت شود. به بیان دیگر، چه ویژگی‌هایی از نمونه‌های مسئلهٔ کوله‌پشتی، باعث می‌شود در زمانی معقولتر نسبت به آنچه در صورت کلی NP-completeِ مطرح است، حل شوند. الگوریتم‌های زیادی بر پایه برنامه‌نویسی پویا، الگوریتم تقسیم و حل یا ترکیبی از هر دو روش برای این مسئله وجود دارند.

مسئلهٔ کوله‌پشتی بیکران

اگر همه وزن‌ها (${\displaystyle w_1,\dots ,w_n,W}$

برای سادگی فرض کنید همه وزن‌ها اکیداً مثبت اند (${\displaystyle w_i>0}$

دقت کنید که ${\displaystyle m[w]}$

• ${\displaystyle m[0]=0}$
  (جمع اعضای مجموعهٔ تهی ۰ است)
• ${\displaystyle m[w]=\underset{w_i\le w}{max}(v_i+m[w-w_i])}$
  که ${\displaystyle v_i}$
  ارزش شی i ام است.

بیشترین ارزش قابل دستیابی از مجموعهٔ تهی، ۰ است. برای محاسبهٔ هر کدام از ${\displaystyle m[w]}$

پیچیدگی زمانی ${\displaystyle O(nW)}$

مسئلهٔ کوله‌پشتی ۰ و ۱

روش مشابهی با استفاده از برنامه‌سازی پویا برای حل مسئله کوله‌پشتی ۰ و ۱ با پیچیدگی زمانی شبه چندجمله‌ای وجود دارد. مانند بالا، فرض کنید ${\displaystyle w_1,w_2,\dots ,w_n,W}$

${\displaystyle m[i,w]}$

• ${\displaystyle m[0,w]=0}$
• ${\displaystyle m[i,0]=0}$
• ${\displaystyle m[i,w]=m[i-1,w]}$
  اگر ${\displaystyle w_i>w}$
• ${\displaystyle m[i,w]=max(m[i-1,w],m[i-1,w-w_i]+v_i)}$
  اگر ${\displaystyle w_i⩽w}$
  .

پاسخ با محاسبهٔ ${\displaystyle m[n,W]}$

الگوریتم دیگری برای مسئله کوله‌پشتی ۰ و ۱ در سال ۱۹۷۴ ارائه شد که گاهی «رویارویی در میانه» نیز نامیده می‌شود. این الگوریتم نسبت به تعداد اشیا نمایی است. (این اسم، از الگوریتمی مشابه در رمزنگاری نشات گرفته‌است). هنگامی که ${\displaystyle W}$

الگوریتم «رویارویی در میانه» به صورت زیر است:

1. مجموعهٔ ${\displaystyle 1,2,\dots ,n}$
   را به دو مجموعهٔ ${\displaystyle A}$
   و ${\displaystyle B}$
   با اندازهٔ نسبتاً برابر تقسیم کنید.
2. ارزش‌ها و وزن‌های هر زیر مجموعه از هریک از ${\displaystyle A}$
   و ${\displaystyle B}$
   را بدست آورید.
3. برای هر زیرمجموعه از ${\displaystyle A}$
   ، بهترین مکمل ${\displaystyle B}$
   را از زیر مجموعه‌هایش انتخاب کنید: به عبارتی زیر مجموعه‌ای از ${\displaystyle B}$
   با بیشترین جمع ارزش کالاها، به نحوی که جمع وزن‌های دو زیر مجموعه، از ${\displaystyle W}$
   بیشتر نشود. بیشترین ارزش بدست آمده را ذخیره کنید.

این الگوریتم از مرتبهٔ حافظهٔ ${\displaystyle O(2^{n/2})}$

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

به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می‌کند (${\displaystyle v_i/w_i}$

در حل مسئلهٔ کوله‌پشتی بیکران، با کنار گذاشتن اشیایی که هیچوقت مورد استفاده قرار نمی‌گیرند، می‌توان مسئله را ساده‌تر کرد. برای نمونه، فرض کنید برای شی‌ای مانند i، می‌توان زیر مجموعه از اشیا به نام J یافت طوری‌که ارزش مجموع آن‌ها بزرگتر از ارزش i و وزن مجموع آن‌ها کمتر از وزن i باشد؛ بنابراین، i نمی‌تواند در جواب بهینه بیاید. در این هنگام مجموعهٔ J را پوشاننده ی i می‌گوییم. (توجه کنید این استدلال برای مسئلهٔ کوله‌پشتی کراندار نمی‌تواند مورد استفاده قرار گیرد. زیرا ممکن است قبلاً از اشیا سازندهٔ مجموعهٔ J استفاده کرده باشیم و تمام شده باشند)

پیدا کردن روابط پوشانندگی به ما کمک می‌کند تا حجم فضای جستجو را به اندازه چشمگیری کاهش دهیم. انواع گوناگون از روابط پوشانندگی وجود دارند که همگی در نامساوی زیر صدق می‌کنند:

${\displaystyle \sum _{j\in J}{w}_j{x}_j\le \alpha w_i}$

که: ${\displaystyle \alpha \in Z_{+},J\subseteq N}$

پوشانندگی انتخابی

شی ${\displaystyle i}$

${\displaystyle \sum _{j\in J}{w}_j{x}_j\le w_i}$

بررسی این نوع پوشانندگی، از لحاظ پیچیدگی محاسباتی چندان ساده نیست، بنابراین از بهترین روش‌ها، راه حل پویاست. در واقع این مسئله، یک مسئله کوله‌پشتی، اما با پارامترهای کوچکتر، مطابق زیر است:

${\displaystyle V=v_i}$

نماد ریاضی پوشانندگی انتخابی به صورت ${\displaystyle i\ll J}$

پوشانندگی حدی

اگر شماری از اشیا نوع ${\displaystyle i}$

${\displaystyle \sum _{j\in J}{w}_j{x}_j\le \alpha w_i}$

این نوع پوشانندگی، نمایش کلی تری از پوشانندگی انتخابی نیست که برای نخستین‌بار در معرفی شد و در الگوریتم EDUK مورد استفاده قرار گرفت. کوچکترین ${\displaystyle \alpha }$

پوشانندگی چندگانه

شی ${\displaystyle i}$

${\displaystyle w_j{x}_j\le w_i}$

که ${\displaystyle J=\{j\},\alpha =1,x_j=\lfloor \frac{w_i}{w_j}\rfloor }$

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

نماد ریاضی پوشانندگی انتخابی به صورت ${\displaystyle i{\ll }_{m}j}$

پوشانندگی ماژولار

فرض کنیم ${\displaystyle b}$

شی ${\displaystyle i}$

${\displaystyle w_j+t{w}_b\le w_i}$

که ${\displaystyle J=\{b,j\},\alpha =1,x_b=t,x_j=1}$

نماد ریاضی پوشانندگی ماژولار به صورت ${\displaystyle i{\ll }_{\equiv }j}$

از انجاییکه این مسئله بهینه‌سازی است، ما رد بهترین مجموعه کنونی کالاها و مجموع ارزش آن‌ها را نگه می‌داریم که اینکار توسط ارائه bestset و و یک متغیر maxprofit انجام می‌شود. این مسئله را برای یافتن نخستین جواب بهینه مطرح می‌کنیم

مسئله:n کالا داریم که هر کدام از آن‌ها دارای ارزشی و وزنی دارند. ارزش‌ها و وزن‌ها، اعدادی صحیح و مثبت هستند. مجموعه‌ای از کالاها با حداکثر مجموع ارزش را طوری تعیین کنید که مجموع اوزان آن‌ها بیش از عدد صحیح مثبت w نشود

ورودی:اعداد صحیح مثبت nوw,ارایه‌های wوpکه از ۱ تاn شاخص دهی شده و هر یک شامل اعداد صحیح و مثبتی هستند که به ترتیب غیر نزولی بر اساس مقادیر [p[i]/w[i مرتب شده‌اند

خروجی:مقدار صحیح maxprofit که بیشترین ارزش است ارائه bestset که از ۱ تا n شاخص دهی شده و در مقادیر bestsetو "yes"است اگر کالای iام در مجموعه بهینه قرار داشته باشد در غیر اینصورت مقدار ان "no" می‌باشد

* void knapsack (index I ,
*            int profit , int weight)
* {
*   if (weight<=W && profit>maxprofit){
*     maxprofit=profit;
*     numbest=i;
*     bestset=include;
*   }
*  if(promising(i)){
*  include[i+1]=”yes”;
* knapsack(i+1,profit+p[i+1],weight+w[i+1]);
* include[i+1]=”no”
* knapsack(i+1,profit,weight);
* }
* }
* bool promising(index i)
* {
* index j,k;
* int totweight;
* float bound;
* if(weight>=W)
* return false;
* else {
* j=i+1;
* bound=profit;
* totweight=weight;
* while(j<=n && totweight + w[j]<=W){
* totweight=totweight+w[j];
* bound=bound+p[j];
* j++;
* }
* k=j;
* if(k<=n)
* bound=bound+(W-totweight)*p[k]/w[k];
* return bound>maxprofit;
* }
* }

طبق قرار دادn,w,p,W ,numbest , bestset , include , maxprofit ورودی‌های روتین نیستند. اگر این متغیرهای را به صورت سراسری تعریف می‌کردیم، شبه کد زیر بیشترین ارزش و مجموعه دارای این ارزش را تولید می‌کرد:

* numbest=0;
* maxprofit = 0 ;
* knapsack(0,0,0);
* cout <<maxprofit;      // نوشتن ماکزیمم ارزش
* for (j=i ; j<=numbest ; j++)     //نمایش مجموعه بهینه کالاها
* cout<<bestset[i];

مسئلهٔ کوله پشتی می‌تواند در تصمیم‌گیری‌هایی که در دنیای واقعی با آن‌ها روبرو هستیم، مورد استفاده قرار گیرد. مانند بریدن کالا به‌طوری‌که کمترین مقدار به هدر رود، انتخاب سرمایه‌گذاری‌ها و سبد سهام، انتخاب دارایی‌ها برای مسئلهٔ امنیت دارایی‌های قبلی و ساختن کلیدها برای سیستم رمزنگاری کوله پشتیِ مرکل-هلمن.

یکی از کاربردهای اولیهٔ مسئلهٔ کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون‌دهنده در پاسخگویی به سؤالات حق انتخاب داشته باشد. چنانچه بارم بندی سؤالات همگن باشد، مسئله بسیار ساده خواهد شد. برای نمونه، اگر آزمون دارای ۱۲ سؤال، هر سؤال به ارزش ۱۰ نمره باشد، آزمون دهنده باید فقط ۱۰ سؤال را پاسخ دهد تا به بیشینه نمره ممکنِ ۱۰۰ برسد. اما برای آزمون‌هایی با بارم بندی نایکسان، مسئله کمی سخت‌تر می‌شود. Feuerman و Weiss سیستمی ارائه دادند که در آن دانش آموزان با آزمونی با بارم بندی ناهمگن، با جمع بارم ۱۲۵ روبرو هستند. از دانش آموزان خواسته می‌شود با توجه به توانایی‌های خود به سؤالات پاسخ دهند. در اینجا با مسئلهٔ کوله پشتی روبرو هستیم. چه زیر مجموعه‌هایی، جمع نمره‌ای برابر با ۱۰۰ خواهند داشت؟ برای هر دانش آموز، پاسخ‌گویی به کدام زیر مجموعه از سؤالات، نمرهٔ بیشتری را به ارمغان می‌آورد؟

صورت مسئله: دزدی قصد سرقت از مغازه‌ای را دارد و حداکثر وزن w از اجناس را که می‌تواند بدزد در این مغازه n نوع جنس وجود دارد. اگر وزن جنس iام wi و قیمت آن vi باشد بیشینه سودی که بدست می‌آورد چقدر است؟

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

۱- صفر و یک

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

ایده حل این مسئله در حالت پویا یه ابن صورت هست که دزد یا جنس iام را برمی‌دارد یا برنمی‌دارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه می‌شود و از مسیری که جواب بیشینه را داده پیش خواهیم رفت. به عبارتی:

 if wi ≥ 0
 max [vi + c[i-1, w-wi], c[i-1, w]}
 if i>0 and w ≥ wi

 for w = 0 to W
 do c[0, w] = 0
 for i = 1 to n
 do c[i, 0] = 0
 for w = 1 to W
 do if wi ≤ w
 then if vi + c[i-1, w-wi]
 then c[i, w] = vi + c[i-1, w-wi]
 else c[i, w] = c[i-1, w]
 else
 c[i, w] = c[i-1, w]

۲-کَسری

در این حالت از مسئه دزد می‌تواند قسمتی از یک جنس را بردارد و مثل حالت قبل ۰ و ۱ی نمی‌باشد. برای این مسئله راه حال حریصانه وجود داره و به این شکل هست که دزد تا می‌تواند جنس پرارزش تر را برداشته و درصورتی که نتوانست بیشترین کسر ممکن آن را برمی‌دارد.

مسئلهٔ کوله پشتی بیش از یک سده مورد مطالعه قرار گرفته و نخستین بررسی در سال ۱۸۹۷ انجام گرفته‌است. هر چند نخستین داده‌های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (۱۸۸۴–۱۹۵۶) Tobias Dantzig باز می‌گردد چیزی با عنوان مسئلهٔ کوله پشتی قبلاً در میان عامهٔ مردم وجود داشته‌است.

مسئلهٔ کوله پشتی درجه دوم، نخستین‌بار توسط Hammer, Gallo و Simeone در سال ۱۹۶۰ مطرح شد.

در سال ۱۹۸۸ پژوهشی از دانشگاه استونی بروک بر روی مجموعه‌ای از الگوریتم‌ها نشان داد که از میان ۷۵ مسئلهٔ الگوریتمی، مسئلهٔ کوله پشتی ۱۸امین مسئلهٔ سرشناس و ۴امین مسئلهٔ پرکاربرد پس از درخت کی‌دی، درخت پسوندی، و مسئله بین پکینگ است.

• فهرست مسائل کوله‌پشتی

• Garey, Michael R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP9, pg.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer. ISBN 3-540-40286-1.
• Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. ISBN 0-471-92420-2.

• https://web.archive.org/web/20090106114038/http://ace.cs.ohiou.edu/~razvan/courses/cs404/lecture16.pdf
• http://www.dreamincode.net/forums/showtopic148124.htm
• http://www.nuigalway.ie/mat/algorithms/knapsack.html
• http://en.wikipedia.org/wiki/Knapsack_problem
• Lecture slides on the knapsack problem
• PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem, with code, benchmarks and downloadable copies of some papers.
• 0-1 Knapsack Problem in Python
• [Martello S. , Toth P. , Knapsack Problems, Algorithms and Computer Implementations. Wiley, New York (1990)]، اس.اس. را ئو . بهینه‌سازی (تئوری و کاربردها ) جلد۲. برگردان: سید محمد مهدی شهیدی‌پور (۱۳۷۳) ص ۸۸۴-۸۵۶، انتشارات دانشگاه فردوسی مشهد.
• حمدی طه. آشنایی با تحقیق در عملیات، برنامه‌ریزی خطی، پویا و با اعداد صحیح، برگردان: محمد باقر بازرگان (۱۳۷۷) ص. ۳۱۸-۳۰۳، نشر دانشگاهی ...-->

• Lecture slides on the knapsack problem
• PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem, with code taking advantage of the dominance relations in an hybride algorithm, benchmarks and downloadable copies of some papers.
• Home page of David Pisinger with downloadable copies of some papers on the publication list (including "Where are the hard knapsack problems?")
• Knapsack Problem solutions in many languages at Rosetta Code
• Dynamic Programming algorithm to 0/1 Knapsack problem
• 0-1 Knapsack Problem in Python
• Interactive JavaScript branch-and-bound solver
• Solving 0-1-KNAPSACK with Genetic Algorithms in Ruby بایگانی‌شده در ۲۳ مه ۲۰۱۱ توسط Wayback Machine