Java 中背包的递归解决方案

Question

HERE背包问题给出了递归解法，但我看不懂。为什么没有检查W？如果 W（剩余重量）低于 0，我们不应该 return 吗？在特定的递归调用中向前迈进有什么意义是 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

权重不能为负数。只有小于或等于总剩余重量时，才减去当前物品的重量。

Answer 2

请注意，在每个递归调用中 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)

Java 中背包的递归解决方案

Recursive solution for Knapsack in Java

java

recursion

knapsack-problem