در این مسئله مجمو عه ای از قطعات داریم که هر یک دارای وزن و ارزش معین است.
- اوزان و ارزش ها اعداد مثبتی هستند.
- دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبتW فراتر رود، کوله پشتی پاره می شود.
الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک
كد:
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”;
knapsachk ( i +1 , profit , weight );
}
}
bool promising ( index i )
{
index j , k ;
int totweight ;
float bound;
if ( weight ≥ W)
return false ;
{
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 > max profit ;
}
}
مقایسه الگوریتم برنامه نویسی پویا و الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک
- تعداد عناصری که توسط الگوریتم برنامه نویسی پویا برای مسئله کوله پشتی صفر و یک محاسبه می شود دربدترین حالت به O (minimum (2ⁿ , nW)) تعلق دارد.
- در بدترین حالت ، الگوریتم عقبگرد (ⁿ 2)θ گره را چک می کند.
- الگوریتم عقبگرد معمولا کارایی بیشتری نسبت به الگوریتم برنامه نویسی پویا دارد.
- هوروویتز و شانی ، روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده الگوریتمی برای مسئله کوله پشتی صفر و یک بسط داده اند که دربدترین حالت به O(2^n/2)
تعلق دارد.