背包但确切重量

Question

是否有算法可以确定背包的确切重量为W？ IE。这就像正常的 0/1 背包问题，n 件物品的重量为 w_i，价值为 v_i。最大化所有物品的价值，但是背包中物品的总重量需要恰好为W!

我知道 "normal" 0/1 背包算法，但这也可以 return 一个重量更轻但价值更高的背包。我想找到最高值但确切的 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

（有什么不明白的就问吧！）

Answer 1

只需在最后一个 else 子句中设置 DP[i][j] = -infinity 即可。

其背后的idea是将递归公式定义稍作改动即可计算：

找到恰好权重 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]，您将永远不会使用它，因为在查找 MAX 时，值 -infinity 将始终被丢弃。

Answer 2

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

通过仅更改初始 dp 状态，而不是算法本身，您可以获得精确重量的背包。

初始化，而不是：

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

应该是：

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

剩下的和你的问题一样。

背包但确切重量

Knapsack but exact weight

java

algorithm

knapsack-problem

dynamic-programming