背包问题：精确重量

Question

有没有一种算法可以确定一个重量恰好为W的背包？即，它就像正常的0/1背包问题一样，有n个物品，每个物品都有重量w_i和价值v_i。最大化所有物品的价值，但是背包中物品的总重量需要恰好为W！

我知道“正常”的0/1背包算法，但是这也可能返回一个重量更轻但价值更高的背包。我想找到重量恰好为W的最高价值。

以下是我的0/1背包实现：

public class KnapSackTest {
    public static void main(String[] args) {
        int[] w = new int[] {4, 1, 5, 8, 3, 9, 2};  //weights
        int[] v = new int[] {2, 12, 8, 9, 3, 4, 3}; //values

        int n = w.length;
        int W = 15; // W (max weight)

        int[][] DP = new int[n+1][W+1];

        for(int i = 1; i < n+1; i++) {
            for(int j = 0; j < W+1; j++) {
                if(i == 0 || j == 0) {
                    DP[i][j] = 0;
                } else if (j - w[i-1] >= 0) {
                    DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j - w[i-1]] + v[i-1]);
                } else {
                    DP[i][j] = DP[i-1][j];
                }
            }
        }
        System.out.println("Result: " + DP[n][W]);
    }
}

这给我带来了：

Result: 29

（如果我的问题不太清楚，请直接问我！）

- zutru

---

只需将DP[i][j] = DP[i-1][j]; 更改为 DP[i][j] = -infinity。 - amit

@老灰胡子 哎呀 - ztv

Answer 1

实际上，被接受的答案是错误的，正如评论中 @Shinchan 发现的那样。

你只需要改变初始的 dp 状态，而不是算法本身，就可以得到精确的重量背包。

初始化的方式应该是：

            if(i == 0 || j == 0) {
                DP[i][j] = 0;
            }

should be:

            if (j == 0) {
                DP[i][j] = 0;
            } else if (i == 0 && j > 0) { // obviously `&& j > 0` is not needed, but for clarity
                DP[i][j] = -inf;
            }

其余部分与您的问题相同。

- Michal Rus

Answer 2

只需在最后的else子句中设置DP[i][j] = -infinity即可解决问题。

其背后的思路是稍微改变递归公式的定义，以计算：

• 找到重量正好为j的物品 i 的最大价值。

现在，归纳假设将发生变化，并且正确性证明与常规背包非常相似，具有以下修改：

DP [i] [j-weight [i]]是可以精确构造为j-weight [i]的最大值，您可以使用项目 i ，给出值DP [i] [j-weight [i]] ，或不采取它，给出值 DP [i-1] [j] - 这是在使用第一个 i-1 个项目的情况下恰好重量j的最大值。

请注意，如果由于某种原因无法构建 DP [i] [j] ，则永远不会使用它，因为查找最大值时始终会丢弃-无穷大的值。

- amit

---

对于weights = {1, 2, 2, 4, 5}，values = {1, 1, 1, 1, 1}和W = 6。它给出的答案是3，而实际上答案是2（因为包括重量为2和4的物品可以得到精确的重量）。你能帮我解决这个问题吗？ - Shinchan