雙包揹包算法

Question

我發現thread爲2包揹包算法提供了僞代碼。 我試過在C++中實現它，但它不工作。這裏是代碼：

#include <cstdio> 
#define MAX_W1 501 
#define MAX_W2 501 

int maximum(int a, int b, int c) { 
    int max = a>b?a:b; 
    return c>max?c:max; 
} 

int knapsack[MAX_W1][MAX_W2] = {0}; 

int main() { 
    int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost 

    scanf("%d %d %d", &n, &s1, &s2); 

    // filing knapsack 
    for (int i = 0; i < n; i++) { 
     scanf("%d %d", &gain, &weight); 

     for (int w1 = s1; w1 >= weight; w1--) { 
      for (int w2 = s2; w2 >= weight; w2--) { 
       knapsack[w1][w2] = maximum(
        knapsack[w1][w2],     // we have best option 
        knapsack[w1 - weight][w2] + gain, // put into sack one 
        knapsack[w1][w2 - weight] + gain // put into sack two 
       ); 
      } 
     } 
    } 

    int result = 0; 

    // searching for result 
    for (int i = 0; i <= s1; i++) { 
     for (int j = 0; j <= s2; j++) { 
      if (knapsack[i][j] > result) { 
       result = knapsack[i][j]; 
      } 
     } 
    } 

    printf("%d\n", result); 

    return 0; 
} 

例如，對於以下輸入：

5 4 3 
6 2 
3 2 
4 1 
2 1 
1 1 

我有輸出：

13 

顯然，這是錯誤的，因爲我可以把所有項目（1,2爲第一袋並休息到第二袋），總和爲16. 我會感謝任何解釋，如果我得到僞代碼錯誤。

我做了小升級，因爲有些人有問題，瞭解輸入格式：

1. 第一行包含3個號碼如下項目的數量，袋一個能力，袋的容量2
2. 後面有n行，每行包含2個數字：增益，第i項的成本。
3. 假設麻袋不能大於500

Answer 1

您正在使用的算法顯示不正確的，因爲它只會考慮在對象恰好適合這兩個麻袋情況。我做了以下修改你的代碼，它現在正確操作：

#include <algorithm> 

using std::max; 

int max3(int a, int b, int c) { 
    return max(a, max(b, c)); 
} 

和

for (int w1 = s1; w1 >= 0; w1--) { 
    for (int w2 = s2; w2 >= 0; w2--) { 
     if (w1 >= weight && w2 >= weight) // either sack has room 
     { 
      knapsack[w1][w2] = max3(
       knapsack[w1][w2],     // we have best option 
       knapsack[w1 - weight][w2] + gain, // put into sack one 
       knapsack[w1][w2 - weight] + gain // put into sack two 
      ); 
     } 
     else if (w1 >= weight) // only sack one has room 
     { 
      knapsack[w1][w2] = max(
       knapsack[w1][w2],     // we have best option 
       knapsack[w1 - weight][w2] + gain // put into sack one 
      ); 
     } 
     else if (w2 >= weight) // only sack two has room 
     { 
      knapsack[w1][w2] = max(
       knapsack[w1][w2],     // we have best option 
       knapsack[w1][w2 - weight] + gain // put into sack two 
      ); 
     } 
    } 
} 

Answer 2

下面是修改代碼，使其工作： -

#include <cstdio> 
#define MAX_W1 501 
#define MAX_W2 501 

int maximum(int a, int b, int c) { 
    int max = a>b?a:b; 
    return c>max?c:max; 
} 

int knapsack[MAX_W1][MAX_W2] = {0}; 

int main() { 
    int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost 

    scanf("%d %d %d", &n, &s1, &s2); 

    // filing knapsack 
    for (int i = 0; i < n; i++) { 
     scanf("%d %d", &gain, &weight); 
    // need to fill up all the table cannot stop if one sack is full because item might fit in other 
     for (int w1 = s1; w1 >= 0; w1--) { 
      for (int w2 = s2; w2 >= 0; w2--) { 
       int val1=0,val2=0; 
       if(weight<=w1) 
        val1 = knapsack[w1 - weight][w2] + gain; 
       if(weight<=w2) 
        val2 = knapsack[w1][w2 - weight] + gain; 

       knapsack[w1][w2] = maximum(
        knapsack[w1][w2],     // we have best option 
        val1,    // put into sack one 
        val2    // put into sack two 
       ); 


      } 
     } 
    } 


    // No need to search for max value it always be Knapsack[s1][s2] 
    printf("%d\n", knapsack[s1][s2]); 

    return 0; 
}