Рекурсивное решение для рюкзака в Java

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. В противном случае этот вес не может быть включен. Эта логика захватывается здесь

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

Как вы можете видеть выше, если новый вес более чем пережиток мы не включаем его за счет снижения стоимости n по 1. Если бы это было меньше, чем W, мы бы вернули Max of Knapsack, включая и не включая его.

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

Answer 2

Вес не может стать отрицательным. Вес искомого предмета вычитается только в том случае, если он меньше или равен суммарному оставшемуся весу.