我添加了背包问题的递归和 DP 的实现。我找不到其中的错误。请帮忙。
import java.util.Scanner;
public class Knapsac {
static int[][] dp;
static int knapsack(int[] size,int[] value, int i, int weight){
if(i <= 0)
return 0;
if(weight < 0)
return Integer.MIN_VALUE;
if(dp[weight][i] != -1)
return dp[weight][i];
dp[weight][i] = Math.max(knapsack(size, value, i-1, weight - size[i]) + value[i], knapsack(size, value, i-1, weight));
return dp[weight][i];
}
static int knapsackWithoutDP(int[] size, int[] value, int i, int weight){
if(i <= 0)
return 0;
if(weight < 0)
return Integer.MIN_VALUE;
return Math.max(knapsackWithoutDP(size, value, i-1, weight - size[i]) + value[i], knapsackWithoutDP(size, value, i-1, weight));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int W, n;
Scanner in = new Scanner(System.in);
W = in.nextInt(); n = in.nextInt();
dp = new int[W+1][n];
for(int i = 0; i < W+1; i++)
for(int j = 0; j < n; j++)
dp[i][j] = -1;
int[] size = new int[n], value = new int[n];
for(int i = 0; i < n; i++){
size[i] = in.nextInt();
value[i] = in.nextInt();
}
System.out.println(knapsackWithoutDP(size, value, size.length-1, W));
System.out.println(knapsack(size, value, size.length-1, W));
}
}
我正在处理测试用例
4 5
1 8
2 4
3 0
2 5
2 3
我应该得到 13 分,但我得到了 12 分。
有人可以帮助我理解我的实现中的错误吗?
最佳答案
问题似乎是您无法选择子集的第一个元素:
if(i <= 0)
return 0;
但这意味着如果您想要包含或排除索引为 0
的项目(这是您可以选择的第一个元素),您将无法到达您选择的位置。 (值[0],重量[0]是添加到背包中的有效选择)
快速解决方法是简单地将此停止子句更改为
if(i < 0) //strictly smaller than
return 0;
关于java - 0-1 背包实现产生错误答案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29193689/