자바 배낭에 대한 재귀 솔루션

Question

HERE 배낭 문제에 대한 재귀 솔루션이 있지만 이해할 수는 없습니다. 왜 W에 대한 수표가 없습니까? W (남은 몸무게)가 0보다 낮 으면 반환하지 않겠습니까? W가 이미 0보다 작은 특정 재귀 호출에서 앞으로 나아갈 시점은 무엇입니까?

// Returns the maximum value that can be put in a knapsack of capacity W 
int knapSack(int W, int wt[], int val[], int n) 
{ 
    // Base Case 
    if (n == 0 || W == 0) 
     return 0; 

    // If weight of the nth item is more than Knapsack capacity W, then 
    // this item cannot be included in the optimal solution 
    if (wt[n-1] > W) 
     return knapSack(W, wt, val, n-1); 

    // Return the maximum of two cases: (1) nth item included (2) not included 
    else return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), 
        knapSack(W, wt, val, n-1) 
       ); 
} 

Answer 1

모든 재귀 호출 값에서 W도 업데이트 중입니다. 그리고 나머지 체중에서 새로운 체중을 뺍니다 W은 W보다 작은 경우에만 빼십시오. 그렇지 않으면 그 무게는 포함될 수 없습니다. 새로운 무게가 남아보다 더 많은 경우 우리가 1에 의해 n의 값을 줄여을 포함하지 않는 이상 알 수 있듯이이 논리는 여기

if (wt[n-1] > W) 
     return knapSack(W, wt, val, n-1); 

캡처됩니다. 그것이 W보다 적 으면 우리는 그것을 포함하여 배낭 맥스를 반환했을 것입니다.

return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), 
        knapSack(W, wt, val, n-1) 

Answer 2

중량이 음수가 될 수 없습니다. 만곡부 품목의 무게는 총 나머지 무게보다 작거나 같은 경우에만 뺍니다.