双背包问题的背包算法

Question

我发现thread提供了两个背包的0/1背包算法伪代码。 我尝试用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. 然后有n行，每行包含两个数字：第i个物品的收益和成本。 3. 假设背包大小不能超过500。

- abc

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
            );
        }
    }
}

- Joe Z

---

感谢您的回答，因为它是正确的，并解释了算法为什么不正确。事实上，当我考虑它时，我真的错过了那种情况。 - abc

如果没有一个袋子有足够的容量（尽管>0）来装载重量，会发生什么情况？我认为这种情况需要考虑。 - rohan-patel

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;
}

- Vikram Bhat

---

在查找数组中的答案时，优化是加一的关键。 - abc

强烈建议对代码的功能进行一些解释。 - Abhijit Sarkar

你如何能够跟踪每个袋子中放入的物品？0-1问题使用第一维来跟踪n，但在这种情况下，它被替换为w1。我尝试过一个三维数组，但不确定如何将n纳入上述算法中。 - Bendrix

@Bendrix 你需要在数组中添加另一个索引，以保存n乘w1乘w2中的所有前n个项目，因为原始问题只是获取最大值，而不考虑所选项目，它通过替换先前的选择来工作，因为我们只关心最后n-1项的最大值。在你的情况下，你可以在外部循环的每次迭代后递增i，并使用上述逻辑计算knapsack[i][w1][w2]，在检索答案时，你必须从knapsack[n-1][w1][w2]向后工作，并选择i，如果knapsack[i-1][w1-w[i]][w2]或knapsack[i-1][w1][w2 - w[i]] + w[i]> knapsack[i-1][w1][w2]。 - Vikram Bhat