我试着自己解决经典的问题。但我得到了一个错误的答案你能帮我找出我做错了什么吗?这里我使用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;
}

10-08 16:28