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

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

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

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

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

تعریف[ویرایش]

مسئله کوله پشتی چیست؟ فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از 1 تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند بصورت مساله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه‌تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است.بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این وجود ،با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100 000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد __________________

فرض کنید n جسم داریم که از 1 تا n شماره گذاری شده‌اند. جسم  i ام ارزشی معادل v_iو وزنی برابر با w_i دارد. معمولاً فرض می شود که وزن ها و ارزش ها نامنفی اند. برای ساده تر شدن نمایش، بدون کم شدن از کلیت مسئله می توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده‌اند. بیشترین وزنی که می توان در کوله پشتی حمل کرد،W است.

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

  • مقدار \qquad \sum_{i=1}^n v_ix_i را بیشینه کنید.
  • به طوری که \qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad  x_i \in \{0,1\}

مسئله ی کوله پشتی کران دار، نسخه ی دیگری از این سوال است که در آن تعداد اشیا (x_i) عددی صحیح و نامنفی و حد اکثر برابر باc_i است. به بیان ریاضی:

  • مقدار \qquad \sum_{i=1}^n v_ix_iرا بیشینه کنید.
  • به طوری که\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad x_i \in \{0,1,\ldots,c_i\}

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

  • یک مسئله تصمیم است.
  • مسئله 0 و 1 است.
  • برای هر شی، وزن و ارزش آن برابرند. یعنیw_i=v_i .

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

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

پیچیدگی محاسباتی[ویرایش]

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

مسئله جمع زیر مجموعه ها که نسخه ای از مسئله ی کلی کوله پشتی است، به عنوان یکی از 21 مسئله ی NP-کامل ِ Karp مطرح است.

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

در خیلی از تحقیقات سعی می شود به این سوال پاسخ داده شود که نمونه های سخت مسئله ی کوله پشتی چه هستند؟ [۱][۲] یا از دید دیگر، چه ویژگی هایی از مثال های مسئله ی کوله پشتی، باعث می شود در زمانی معقولتر نسبت به آن چه در صورت کلی NP-completeِ سوال مطرح است، حل شوند. .[۳] الگوریتم های زیادی بر پایه ی: برنامه نویسی پویا,[۴] روش تقسیم و حد، [۵] یا ترکیبی از هر دو روش[۳][۶][۷][۸] برای این مسئله وجود دارند.

راه حل برنامه نویسی پویا[ویرایش]

مسئله ی کوله پشتی بیکران[ویرایش]

اگر تمام وزن ها (w_1,\ldots,w_n,W ) اعداد صحیح نامنفی باشند، مسئله ی کوله پشتی در در زمانی شبه چند جمله ای با استفاده از برنامه نویسی پویا قابل حل است.

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

دقت کنید که m[w] ویژگی های زیر را دارد:

  • m[0]=0\,\! (جمع اعضای مجموعه ی تهی 0 است)
  • m[w]= \max_{w_i \le w}(v_i+m[w-w_i]) که v_i ارزش شی i ام است.

بیشترین ارزش قابل دستیابی از مجموعه ی تهی، 0 است. برای محاسبه ی هر کدام از  m[w] ها، باید n شی را بررسی کرد. همچنین آرایه ی W، m عنصر دارد. بنابر این زمان اجرای این الگوریتم O(nW) است. بدیهی است با تقسیم کردن w_1,\,w_2,\,\ldots,\,w_n,\,W بر بزرگترین مقسوم علیه مشترک شان، می توان زمان اجرای الگوریتم را بهینه کرد.

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

مسئله ی کوله پشتی 0 و 1[ویرایش]

روش مشابهی با استفاده از برنامه سازی پویا برای حل مسئله کوله پشتی 0 و 1 با پیچیدگی زمانی شبه چندجمله ای وجود دارد. مانند بالا، فرض کنید w_1,\,w_2,\,\ldots,\,w_n,\,W ها اعداد صحیح اکیداً مثبتی هستند. m[i,w] را بیشترین ارزش قابل دستیابی، با استفاده از اشیای 1 تا i با حد اکثر وزن w تعریف کنید.

m[i,w] را می توان به طور بازگشتی، مطابق زیر تعریف کرد:

  • m[0,\,w]=0
  • m[i,\,0]=0
  • m[i,\,w]=m[i-1,\,w] اگر w_i> w\,\!
  • m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i) اگر w_i \leqslant w.

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

الگوریتم دیگری برای مسئله کوله پشتی 0 و 1، در سال 1974 ارائه شد[۹] که گاهی "رویارویی در میانه" نیز نامیده می شود. این الگوریتم نسبت به تعداد اشیا نمایی است. (این اسم، از الگوریتمی مشابه در رمزنگاری نشات گرفته است). هنگامی که W نسبت به n بسیار بزرگتر باشد ( یعنیW از 2^n هم بزرگتر باشد)، این الگوریتم نسبت به روش پویا از نظر زمانی بهینه تر است. برای مثال فرض کنید w_i ها نامنفی باشند، اما صحیح نباشند. در اینجا نیز می توان از روش پویا استفاده کرد: اگر عدد ها d رقم بعد از اعشار داشته باشند، کافی است آنها را در 10^d ضرب و سپس رند کرد (با استفاده از محاسبات ممیز ثابت ). روش پویا با این تغییرات، از مرتبه ی زمانی O(nW*10^d) و حافظه ی O(W*10^d) خواهد بود.

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

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

این الگوریتم از مرتبه ی حافظه ی O(2^{n/2}) است و با پیاده سازی بهینه گام 3، از مرتبه ی زمانی O(n*2^{n/2}) می شود. (برای مثال با مرتب کردن زیرمجموعه های B بر حسب وزن، چشم پوشی از زیر مجموعه هایی از B که وزنی بیشتر از سایر زیر مجموعه ها با ارزش بزرگتر/مساوی دارند و استفاده از جستجوی دودویی برای یافتن بهترین تطابق). مانند روش رویارویی در میانه در رمز نگاری، استفاده از این الگوریتم با هزینه کردن حافظه (مرتبه ی نمایی به جای مقدار ثابت) باعث بهینه شدن زمان اجرا می شود. می دانیم چنانچه بخواهیم تمام زیر مجموعه های {1...n} را به روش brute force بررسی کنیم، مرتبه ی زمانی O(n*2^n) خواهد شد اما با این الگوریتم آن را بهینه کردیم.

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

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

به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می کند (v_i/w_i) سپس از شی شماره 1 شروع می کند.بیشترین تعداد ممکن از آن را در کوله پشتی قرار می دهد، تا زمانی که دیگر جای خالی ای برای آن نوع باقی نماند. آنگاه سراغ شی بعدی میرود. ( دقت کنید که در این نسخه از سوال، محدودیتی برای تعداد اشیا نداریم) اگر m بیشینه ارزش اشیایی باشد که در کوله پشتی جا می شوند، این الگوریتم حداقل به مقدار m/2 دست می یابد. اما اگر تعداد مجاز از هر شی محدود باشد، ممکن است خروجی این الگوریتم از پاسخ بهینه بسیار دور باشد.

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

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

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

\qquad \sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i, and \qquad \sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\, for some x \in Z _+^n

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

پوشانندگی انتخابی[ویرایش]

شی  i ام، به طور انتخابی توسط  J پوشانده شده، اگر جمع وزن تعدادی از اعضای مجموعه ی  J ، کمتر از  w_i باشد و جمع ارزش آنها بیشتر از v_i . به بیان ریاضی:

\qquad \sum_{j \in J} w_j\,x_j \ \le  w_i و \qquad \sum_{j \in J} v_j\,x_j \ \ge v_i درصورتی که x \in Z _+^n که \alpha=1 .

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

V=v_i ، W=w_i و اشیا محدود به مجموعه ی J هستند.

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

پوشانندگی حدی[ویرایش]

شی  i ام، به طور حدی توسط  J پوشانده شده، اگر تعدادی از اشیا نوع  i توسط  J پوشانده شوند. به بیان ریاضی:

\qquad \sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i و \qquad \sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\, در صورتی که x \in Z _+^n و \alpha\geq 1 .

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

پوشانندگی چندگانه[ویرایش]

شی  i ، به طور چندگانه توسط شی  j پوشانده شده، اگر  i توسط تعدادی از شی نوع  j پوشانده شود. (یعنی شی  i ، فقط توسط تعدادی شی از نوع  j پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد). به بیان ریاضی:

\qquad w_j\,x_j \ \le  w_i و \qquad v_j\,x_j \ \ge v_i برای x_j \in Z _+

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

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

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

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

فرض کنیم  b بهترین شی باشد، یعنی برای تمام  i ها ، \frac{v_b}{w_b}\ge\frac{v_i}{w_i}\, .  b شی ای با بیشترین چگالی است.

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

 w_j+tw_b \le w_i و v_j +tv_b \ge v_i

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

نماد ریاضی پوشانندگی ماژولار به صورت 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]=0         *
                                                                                                                                                      ;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       *
                                                                                                                                                            {*

شبه کد عقبگرد برای مسئله کوله پشتی 0و1[ویرایش]

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

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

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

خروجی:مقدار صحیح maxprofit که ماکزیمم ارزش است , ارایه bestset که از 1 تا 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];

کاربرد ها[ویرایش]

مسئله ی کوله پشتی می تواند در تصمیم گیری هایی که در دنیای واقعی با آن ها روبرو هستیم، مورد استفاده قرار گیرد. مانند بریدن کالا به طوری که کمترین مقدار به هدر رود، [۱۱] انتخاب سرمایه گذاری ها و سبد سهام، [۱۲] انتخاب دارایی ها برای مسئله ی امنیت دارایی های قبلی[۱۳] و ساختن کلیدها برای سیستم رمزنگاری کوله پشتی ِ مرکل-هلمن.[۱۴]

== یکی از کاربرد های اولیه ی مسئله ی کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون دهنده در پاسخگویی به سوالات حق انتخاب داشته باشد. چنانچه بارم بندی سوالات همگن باشد، مسئله بسیار ساده خواهد شد.برای مثال، اگر آزمون دارای 12 سوال، هر سوال به ارزش 10 نمره باشد، آزمون دهنده باید فقط 10 سوال را پاسخ دهد تا به بیشینه نمره ممکنِ 100 برسد. اما برای آزمون هایی با بارم بندی نایکسان، مسئله کمی سخت تر می شود. Feuerman و Weiss سیستمی ارائه دادند که در آن دانش آموزان با آزمونی با بارم بندی ناهمگن، با جمع بارم 125 روبرو هستند. از دانش آموزان خواسته می شود با توجه به توانایی های خود به سوالات پاسخ دهند. در اینجا با مسئله ی کوله پشتی روبرو هستیم. چه زیر مجموعه هایی، جمع نمره ای برابر با 100 خواهند داشت؟ برای هر دانش آموز، پاسخ گویی به کدام زیر مجموعه از سوالات، نمره ی بیشتری را به ارمغان می آورد؟[۱۵]

یک مثال از مسئله کوله پشتی[ویرایش]

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

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

ایده حل این مسئله در حالت پویا یه ابن صورت هست که دزد یا جنس 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]

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

تاریخچه[ویرایش]

مسئله ی کوله پشتی بیش از یک قرن مورد مطالعه قرار گرفته و اولین بررسی در سال 1897 انجام گرفته است.[۱۶] هر چند اولین داده های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (1884–1956) Tobias Dantzig برمی گردد، چیزی با عنوان مسئله ی کوله پشتی قبلاً در میان عامه ی مردم وجود داشته است. [۱۷]

مسئله ی کوله پشتی درجه دوم، اولین بار توسط Hammer ، Gallo و Simeone در سال 1960 مطرح شد.[۱۸]

در سال 1988، تحقیقی از دانشگاه استونی بروک بر روی مجموعه ای از الگوریتم ها، نشان داد که از میان 75 مسئله ی الگوریتمی، مسئله ی کوله پشتی، 18 امین مسئله ی معروف و 4 امین مسئله ی پرکاربرد بعد از درخت کی دی، درخت پیشوندی و bin packing problem است. [۱۹]

برای مطالعه[ویرایش]

یادداشت ها[ویرایش]

  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  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. 
  16. Mathews, G. B. (25 June 1897). "On the partition of numbers". 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". AGM SIGACT News 30 (3): 65–74. ISSN 0163-5700. 

منابع[ویرایش]

پیوند به بیرون[ویرایش]