نمايش پست تنها
قديمي ۰۸-۱-۱۳۸۸, ۰۷:۴۵ بعد از ظهر   #4 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink مسئله کوله پشتی صفر و یک

در این مسئله مجمو عه ای از قطعات داریم که هر یک دارای وزن و ارزش معین است.

- اوزان و ارزش ها اعداد مثبتی هستند.

- دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبت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)
تعلق دارد.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
daniel_atish (۰۳-۱-۱۳۹۳), mahdiheart (۰۶-۲۰-۱۳۹۳), raha90 (۰۳-۸-۱۳۹۰), ایمان رئال (۰۳-۱۱-۱۳۹۱)