背包但精确重量

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

Answer 1

只需在最后一个els子句中设置dp[i][j]=-infinity，就可以实现这一目的。

其背后的IDE是稍微改变递归公式定义来计算：

• 用精确的权重j到项i找到最大值。

现在，归纳法假设将发生变化，对正确性的证明将非常类似于规则背包，进行如下修改：

dp[i][j-weight[i]]现在是可以精确地用j-weight[i]构造的最大值，您可以取项i，给出dp[i][j-weight[i]]的值，也可以不取项，给出dp[i-1][j]-这是对第一个i-1项精确地使用weightj时的最大值。

请注意，如果由于某种原因无法构造dp[i][j]，则永远不会使用它，因为在查找max时总是会丢弃值无穷大。