我试着自己解决经典的问题。但我得到了一个错误的答案你能帮我找出我做错了什么吗?这里我使用108
。
重量限制是10
答案是5+3+2==>25+15+14=54
public class KnapSack {
public static int[] weight={6,5,4,3,2};
public static int[] value={12,25,24,15,14};
public static void main(String[] args) {
System.out.println(c(0,0,10));
}
public static int c(int currentElement,int currentValue,int currentReamainder){
int p = 0;
if(currentReamainder<=0) return currentValue;
for(int i=currentElement;i<weight.length;i++){
if(currentReamainder<weight[i]) return currentValue;
p = Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder))
}
return p;
}
}
更新:
我该怎么打印最优解的权重?
最佳答案
你的错误是这一行
p=Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder));
应该是
int val = Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder));
p = Math.max(val, p);
最后一个bug是当您同时更新
currentValue
并返回p
时,那么想象一下最后一个调用,当函数返回currentValue
时,加上每个步骤中的最后一个value[i]
,那么您的结果是双重的所以,您的函数应该是(注意,我删除了
currentValue
参数,这是不必要的):public static int c(int currentElement,int currentReamainder){
int p = 0;
if(currentReamainder<=0) return 0;
for(int i=currentElement;i<weight.length;i++){
if(currentReamainder<weight[i]) break;//This line is not valid, only when the weight array is sorted(ascending order)
int val = Math.max(value[i]+c(i+1,currentReamainder-weight[i]),c(i+1,currentReamainder));
p = Math.max(val, p);
}
return p;
}