배낭 동적 프로그래밍 디버깅

Question

나는 고전적인 knapsap problem을 풀려고 노력했다. 그러나 나는 잘못된 대답을 108으로 받고 있습니다. 내가 잘못한 것을 알아낼 수있게 도와 주시겠습니까? 여기에서 나는 recursion을 사용하고있다.

무게 제한은 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; 
} 

} 

업데이트 : 나는의 가중치를 인쇄하려면 어떻게해야합니까 최적 해?

Answer 1

귀하의 오류가 때 모두 currentValue를 업데이트하고 동시에 p를 반환, 그래서 마지막 호출을 상상할 때 마지막 버그가

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); 

해야

p=Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder)); 

이 라인 함수는 currentValue과 각 단계에서 마지막으로 value[i]을 반환하므로 결과는 double입니다.

그럼, 당신의 기능은 (내가 필요하지 않습니다 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; 
}