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

نمونه‌ای از مسئلهٔ کوله‌پشتی یک بعدی: چه جعبه‌هایی باید انتخاب شوند تا مقدار پول بیشینه شود اما وزن جعبه‌های مذکور بیشتر از ۱۵ کیلوگرم نشود؟ یک مسئله چند محدودیتی، می‌تواند هم وزن و هم حجم جعبه‌ها را در نظر بگیرد. مدل‌سازی اندازه و شکل جعبه‌ها، یک مسئله بسته‌بندی است.
(راه حل: اگر هر تعداد دلخواهی از جعبه‌ها در دسترس باشد، ۳ جعبهٔ زرد و ۳ جعبهٔ خاکستری پاسخ‌اند. اما اگر مانند شکل باشد یعنی از هر جعبه فقط یکی داشته باشیم، همه جعبه‌ها به جز جعبهٔ سبز را انتخاب می‌کنیم)

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

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

نسخهٔ مسئله تصمیم برای مسئلهٔ کوله‌پشتی، این سؤال است: «آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر یا مساوی W قابل دستیابی است؟»

تعریف

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

فرض کنید ${\displaystyle n}$ جسم داریم که از ${\displaystyle 1}$ تا ${\displaystyle n}$ شماره‌گذاری شده‌اند. جسم ${\displaystyle i}$ ام ارزشی معادل ${\displaystyle v_{i}}$و وزنی برابر با ${\displaystyle w_{i}}$ دارد. معمولاً فرض می‌شود که وزن‌ها و ارزش‌ها نامنفی‌اند. برای ساده‌تر شدن نمایش، بدون کم شدن از کلیت مسئله می‌توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده‌اند. بیشترین وزنی که می‌توان در کوله‌پشتی حمل کرد،${\displaystyle W}$ است.

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

• مقدار ${\displaystyle \qquad \sum _{i=1}^{n}v_{i}x_{i}}$ را بیشینه کنید.
• به‌طوری‌که ${\displaystyle \qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1\}}$

مسئلهٔ کوله‌پشتی کران‌دار نسخهٔ دیگری از این سؤال است که در آن تعداد اشیا (${\displaystyle x_{i}}$) عددی صحیح و نامنفی و حداکثر برابر با${\displaystyle c_{i}}$ است. به بیان ریاضی:

• مقدار ${\displaystyle \qquad \sum _{i=1}^{n}v_{i}x_{i}}$را بیشینه کنید.
• به‌طوری که${\displaystyle \qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1,\ldots ,c_{i}\}}$

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

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

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

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

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

در این روش (knapsack (int n,int W برابر با حل مسئله در نظر گرفته می‌شود که از میان ${\displaystyle n}$ شی با محدودیت ظرفیتی ${\displaystyle W}$ تعدادی شی انتخاب می‌کنیم. اگر ${\displaystyle (x_{1},x_{2},...,x_{n})}$ اشیا بهینهٔ مد نظر باشد داریم:

۱. اگر ${\displaystyle x_{n}=0}$ تابع به صورت (knapsack(int ${\displaystyle n-1}$,int ${\displaystyle W}$ صدا زده می‌شود.

۲. اگر ${\displaystyle x_{n}=1}$ تابع به صورت (knapsack(int ${\displaystyle n-1}$,int ${\displaystyle W-x_{n}}$صدا زده می‌شود.

حال اگر ${\displaystyle C[n,W]}$ را برابر با ارزش راه حل بهینهٔ مسئله در نظر بگیریم داریم:

${\displaystyle C[n,W]=max(profitsforcase1,profitsforcase2)=max(C[n-1,W],C[n-1,W-w_{n}]+p_{n})}$

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

${\displaystyle C[n,W]=max(C[n-2,W],C[n-2,W-w_{n-1}]+p_{n-1})}$

#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},\ldots ,w_{n},W}$) اعداد صحیح نامنفی باشند مسئلهٔ کوله‌پشتی در زمانی شبه چندجمله‌ای با استفاده از برنامه‌نویسی پویا قابل حل است.

برای سادگی فرض کنید همه وزن‌ها اکیداً مثبت اند (${\displaystyle w_{i}>0}$). می‌خواهیم جمع ارزش کالاهای انتخاب شده را بیشینه کنیم با این فرض که مجموع وزن آن‌ها حداکثر${\displaystyle W}$ شود. حال برای هر ${\displaystyle w<W}$، مقدار ${\displaystyle m[w]}$ را بیشترین ارزش قابل دستیابی تعریف کنید به‌طوری‌که جمع وزن اشیا انتخاب شده حداکثر ${\displaystyle w}$ شود. بدیهی است که ${\displaystyle m[W]}$ پاسخ مورد نظر است.

دقت کنید که ${\displaystyle m[w]}$ ویژگی‌های زیر را دارد:

• ${\displaystyle m[0]=0\,\!}$ (جمع اعضای مجموعهٔ تهی ۰ است)
• ${\displaystyle m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])}$ که ${\displaystyle v_{i}}$ ارزش شی i ام است.

بیشترین ارزش قابل دستیابی از مجموعهٔ تهی، ۰ است. برای محاسبهٔ هر کدام از ${\displaystyle m[w]}$ها، باید ${\displaystyle n}$ شی را بررسی کرد. همچنین آرایهٔ ${\displaystyle W}$، ${\displaystyle m}$ عنصر دارد؛ بنابراین زمان اجرای این الگوریتم ${\displaystyle O(nW)}$ است. بدیهی است با تقسیم کردن ${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$ بر بزرگ‌ترین مقسوم علیه مشترک می‌توان زمان اجرای الگوریتم را بهینه کرد.

پیچیدگی زمانی ${\displaystyle O(nW)}$ تناقضی با NP-complete بودن مسئلهٔ کوله‌پشتی ندارد؛ زیرا ${\displaystyle W}$ برخلاف ${\displaystyle n}$، برحسب ورودی چندجمله‌ای نیست. طول ${\displaystyle W}$ ِ ورودی، متناسب با تعداد بیت‌های لازم برای نمایش ${\displaystyle W}$، یعنی ${\displaystyle \log W}$ است، نه خود ${\displaystyle W}$.

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

روش مشابهی با استفاده از برنامه‌سازی پویا برای حل مسئله کوله‌پشتی ۰ و ۱ با پیچیدگی زمانی شبه چندجمله‌ای وجود دارد. مانند بالا، فرض کنید ${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$ها اعداد صحیح اکیداً مثبتی هستند. ${\displaystyle m[i,w]}$ را بیشترین ارزش قابل دستیابی، با استفاده از اشیای ۱ تا ${\displaystyle i}$ با حداکثر وزن ${\displaystyle 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}\leqslant w}$.

پاسخ با محاسبهٔ ${\displaystyle m[n,W]}$ به‌دست می‌آید. برای کارآمد شدن راه حل، می‌توان از جدولی برای نگهداری نتایج محاسبات قبلی استفاده کرد؛ بنابراین پیچیدگی زمانی آن ${\displaystyle O(nW)}$ و حافظه ${\displaystyle O(nW)}$ خواهد شد. همچنین می‌توان حجم حافظه را به ${\displaystyle O(W)}$ کاهش داد. به این ترتیب که آرایهٔ یک بعدی${\displaystyle m[w]}$، ارزش بهینه تاکنون را نشان می‌دهد. از ${\displaystyle i=1}$ شروع کرده، آرایه را پر می‌کنیم. سپس با حرکت بر روی ${\displaystyle i}$، مقدار ${\displaystyle m[w]}$ را با افزودن یک شی جدید به انتخاب‌ها، به روز آوری می‌کنیم.

الگوریتم دیگری برای مسئله کوله‌پشتی ۰ و ۱ در سال ۱۹۷۴ ارائه شد^[۹] که گاهی «رویارویی در میانه» نیز نامیده می‌شود. این الگوریتم نسبت به تعداد اشیا نمایی است. (این اسم، از الگوریتمی مشابه در رمزنگاری نشات گرفته است). هنگامی که ${\displaystyle W}$ نسبت به ${\displaystyle n}$ بسیار بزرگتر باشد (یعنی${\displaystyle W}$ از ${\displaystyle 2^{n}}$ هم بزرگتر باشد) این الگوریتم نسبت به روش پویا از نظر زمانی بهینه تر است. برای نمونه فرض کنید ${\displaystyle w_{i}}$ها نامنفی باشند اما صحیح نباشند. در اینجا نیز می‌توان از روش پویا استفاده کرد: اگر عددها ${\displaystyle d}$ رقم بعد از اعشار داشته باشند کافی است آن‌ها را در ${\displaystyle 10^{d}}$ ضرب و سپس رند کرد (با استفاده از محاسبات ممیز ثابت). روش پویا با این تغییرات، از مرتبهٔ زمانی ${\displaystyle O(nW*10^{d})}$ و حافظهٔ ${\displaystyle O(W*10^{d})}$ خواهد بود.

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

1. مجموعهٔ ${\displaystyle {1,2,\ldots ,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 O(n*2^{n/2})}$ می‌شود. (برای نمونه با مرتب کردن زیرمجموعه‌های ${\displaystyle B}$ بر حسب وزن، چشم پوشی از زیر مجموعه‌هایی از ${\displaystyle B}$ که وزنی بیشتر از سایر زیر مجموعه‌ها با ارزش بزرگتر/مساوی دارند و استفاده از جستجوی دودویی برای یافتن بهترین تطابق). مانند روش رویارویی در میانه در رمز نگاری، استفاده از این الگوریتم با هزینه کردن حافظه (مرتبهٔ نمایی به جای مقدار ثابت) باعث بهینه شدن زمان اجرا می‌شود. می‌دانیم چنانچه بخواهیم همه زیر مجموعه‌های {۱...n} را به روش brute force بررسی کنیم، مرتبهٔ زمانی ${\displaystyle O(n*2^{n})}$ خواهد شد اما با این الگوریتم آن را بهینه کردیم.

الگوریتم تقریبی حریصانه

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

به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می‌کند (${\displaystyle v_{i}/w_{i}}$) سپس از شی شماره ۱ شروع می‌کند. بیشترین تعداد ممکن از آن را در کوله‌پشتی قرار می‌دهد، تا زمانی که دیگر جای خالی‌ای برای آن نوع باقی نماند. آنگاه سراغ شی بعدی می‌رود. (دقت کنید که در این نسخه از سؤال، محدودیتی برای تعداد اشیا نداریم) اگر ${\displaystyle m}$ بیشینه ارزش اشیایی باشد که در کوله‌پشتی جا می‌شوند، این الگوریتم حداقل به مقدار ${\displaystyle m/2}$ دست می‌یابد. اما اگر تعداد مجاز از هر شی محدود باشد، ممکن است خروجی این الگوریتم از پاسخ بهینه بسیار دور باشد.

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

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

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

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$، and ${\displaystyle \qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$ for some ${\displaystyle x\in Z_{+}^{n}}$

که: ${\displaystyle \alpha \in Z_{+}\,,J\subseteq N}$ و ${\displaystyle i\not \in J}$. و ${\displaystyle x_{j}}$ تعداد انتخاب‌های شی نوع j را نشان می‌دهد. (دقت کنید این jها، اعضای مجموعهٔ J هستند)

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

شی ${\displaystyle i}$ ام به‌طور انتخابی توسط ${\displaystyle J}$ پوشانده شده، اگر جمع وزن شماری از اعضای مجموعهٔ ${\displaystyle J}$، کمتر از ${\displaystyle w_{i}}$ باشد و جمع ارزش آن‌ها بیشتر از ${\displaystyle v_{i}}$. به بیان ریاضی:

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$ و ${\displaystyle \qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$ درصورتی که ${\displaystyle x\in Z_{+}^{n}}$ که ${\displaystyle \alpha =1}$.

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

${\displaystyle V=v_{i}}$، ${\displaystyle W=w_{i}}$ و اشیا محدود به مجموعهٔ ${\displaystyle J}$ هستند.

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

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

اگر شماری از اشیا نوع ${\displaystyle i}$ توسط ${\displaystyle J}$ پوشانده شوند شی ${\displaystyle i}$ ام، تا اندازه‌ای توسط ${\displaystyle J}$ پوشانده می‌شود. به بیان ریاضی:

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$ و ${\displaystyle \qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$ در صورتی که ${\displaystyle x\in Z_{+}^{n}}$ و ${\displaystyle \alpha \geq 1}$.

این نوع پوشانندگی، نمایش کلی تری از پوشانندگی انتخابی نیست که برای نخستین‌بار در^[۴] معرفی شد و در الگوریتم EDUK مورد استفاده قرار گرفت. کوچک‌ترین ${\displaystyle \alpha }$ ممکن، حد ${\displaystyle i}$ نامیده می‌شود. به بیان ریاضی: ${\displaystyle t_{i}=(\alpha -1)w_{i}}$. در این هنگام، پاسخ بهینه حداکثر می‌تواند به تعداد ${\displaystyle \alpha -1}$ شی، از نوع ${\displaystyle i}$ را شامل شود.

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

شی ${\displaystyle i}$، به‌طور چندگانه توسط شی ${\displaystyle j}$ پوشانده شده، اگر ${\displaystyle i}$ توسط شماری از شی نوع ${\displaystyle j}$ پوشانده شود. (یعنی شی ${\displaystyle i}$، فقط توسط تعدادی شی از نوع ${\displaystyle j}$ پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد). به بیان ریاضی:

${\displaystyle \qquad w_{j}\,x_{j}\ \leq w_{i}}$ و ${\displaystyle \qquad v_{j}\,x_{j}\ \geq v_{i}}$ برای ${\displaystyle x_{j}\in Z_{+}}$

که ${\displaystyle J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor }$.

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

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

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

فرض کنیم ${\displaystyle b}$ بهترین شی باشد یعنی برای همه ${\displaystyle i}$ها ${\displaystyle {\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,}$. ${\displaystyle b}$ شی‌ای با بیشترین چگالی است.

شی ${\displaystyle i}$ ام، به‌طور ماژولار توسط شی ${\displaystyle j}$ پوشانده شده، اگر توسط ${\displaystyle j}$ و تعدادی شی از نوع ${\displaystyle b}$ پوشانده شود. (یعنی شی ${\displaystyle i}$، فقط توسط ${\displaystyle j}$ و تعدادی شی از نوع ${\displaystyle b}$ پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد) به بیان ریاضی:

${\displaystyle w_{j}+tw_{b}\leq w_{i}}$ و ${\displaystyle v_{j}+tv_{b}\geq v_{i}}$

که ${\displaystyle J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1}$.

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

الگوریتم کوله‌پشتی با استفاده از روش حریصانه

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<n;i++)
    x[i]=۰
    U=W
    for(i=0;i<n;i++)
 if(W[i]>u);
break ;
[
x[i]=1;
u=u-[wi]
}
if(i<n)
    x[i]=u/w
}

شبه کد عقبگرد برای مسئله کوله‌پشتی ۰ و ۱

از آنجایی که این مسئله بهینه‌سازی است، ما رد بهترین مجموعه کنونی کالاها و مجموع ارزش آن‌ها را نگه می‌داریم که اینکار توسط ارائه 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ام را برمی‌دارد یا برنمی‌دارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه می‌شود و از مسیری که جواب بیشینه را داده پیش خواهیم رفت. به عبارتی:

کد c[i,w] = c[i-1, w]

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

شبه کد Dynamic-0-1-knapsack (v, w, n, W)

 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 در سال ۱۹۶۰ مطرح شد.^[۱۸]

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

جستارهای وابسته

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

پانویس

1. Pisinger, D. 2003. Where are the hard knapsack problems? Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark.
2. L. Caccetta, A. Kulanoot, Computational Aspects of Hard Knapsack Problems, Nonlinear Analysis 47 (2001) 5547–5558.
3. Vincent Poirriez, Nicola Yanev, Rumen Andonov (2009) A Hybrid Algorithm for the Unbounded Knapsack Problem Discrete Optimization http://dx.doi.org/10.1016/j.disopt.2008.09.004
4. Rumen Andonov, Vincent Poirriez, Sanjay Rajopadhye (2000) Unbounded Knapsack Problem: dynamic programming revisited European Journal of Operational Research 123: 2. 168–181 http://dx.doi.org/10.1016/S0377-2217(99)00265-9
5. S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementation, John Wiley and Sons, 1990
6. S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem , Manag. Sci. , 45:414–424, 1999.
7. G. Plateau, M. Elkihel, A hybrid algorithm for the 0-1 knapsack problem, Methods of Oper. Res. , 49:277–293, 1985.
8. S. Martello, P. Toth, A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Manag. Sci. , 30:765–771
9. Horowitz, Ellis; Sahni, Sartaj (1974), "Computing partitions with applications to the knapsack problem", Journal of the Association for Computing Machinery, 21: 277–292, doi:10.1145/321812.321823 {{citation}}: Unknown parameter |:en:mr= ignored (help)
10. George B. Dantzig, Discrete-Variable Extremum Problems, Operations Research Vol. 5, No. 2, April 1957, pp. 266–288, DOI: http://dx.doi.org/10.1287/opre.5.2.266
11. Kellerer, Pferschy, and Pisinger 2004, p. 449
12. Kellerer, Pferschy, and Pisinger 2004, p. 461
13. Kellerer, Pferschy, and Pisinger 2004, p. 465
14. Kellerer, Pferschy, and Pisinger 2004, p. 472
15. Feuerman, Martin; Weiss, Harvey (April 1973). "A Mathematical Programming Model for Test Construction and Scoring". Management Science. 19 (8): 961–966. {{cite journal}}: Unknown parameter |:en:jstor= ignored (help)
16. Mathews, G. B. (25 June 1897). "On the partition of numbers" (PDF). Proceedings of the London Mathematical Society. 28: 486–490.
17. Kellerer, Pferschy, and Pisinger 2004, p. 3
18. Gallo, G. ; Hammer, P. L. ; Simeone, B. (1980). "Quadratic knapsack problems". Mathematical Programming Studies. 12: 132–149. doi:10.1007/BFb0120892.^{[پیوند مرده]}
19. Skiena, S. S. (September 1999). "Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository" (PDF). AGM SIGACT News. 30 (3): 65–74. ISSN 0163-5700.

منابع

• Garey, Michael R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help) A6: MP9, pg.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer. ISBN 3-540-40286-1. {{cite book}}: Unknown parameter |:en:mr= ignored (help)
• Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. ISBN 0-471-92420-2. {{cite book}}: Unknown parameter |:en:mr= ignored (help)
• 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