背包但确切的重量-Java 学习之路

是否有算法来确定具有精确重量W的背包？即这就像正常的0/1背包问题，n个项目各有权重w_i和值v_i . 最大化所有项目的 Value ，但是 total weight of the items in the knapsack need to have exactly weight W ！

我知道“普通”0/1背包算法，但这也可以返回一个重量更轻但 Value 更高的背包 . 我想找到最高值但确切的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

（请问我的问题中是否有任何不清楚的地方！）

2 回答

0
只需在上一个 else 子句中设置 DP[i][j] = -infinity 即可 .

它背后的想法是稍微改变递归公式定义来计算：
- 使用 exactly 权重 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 .
回复于 2024-04-25T19:34:50+08:00
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;
            }
```
剩下的就像你的问题一样 .
回复于 2024-04-25T19:34:50+08:00

背包但确切的重量

2 回答

相关问题