gpt4 book ai didi

java - 背包但确切重量

转载 作者:塔克拉玛干 更新时间:2023-11-02 19:09:37 24 4
gpt4 key购买 nike

是否有一种算法可以确定背包的确切重量为 W? IE。这就像正常的 0/1 背包问题,n 件元素的重量分别为 w_i 和值(value) v_i。最大化所有元素的值(value),但是背包中元素的总重量需要恰好为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

(请问我的问题有什么不清楚的!)

最佳答案

实际上,正如@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;
}

其余的保持在你的问题中。

关于java - 背包但确切重量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47608725/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com