0/1背包问题的代码不起作用

Question

这是我使用的代码：

class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
         // your code here 
         int[] dp=new int[W+1];
         dp[0]=0;
         for(int i=0;i<wt.length;i++){
             for(int j=wt[i];j<=W;j++){
                 dp[j]=Math.max(dp[j],val[i]+dp[j-wt[i]]);
             }
         }
    return dp[W];
         
    } 
}

此代码给出了错误的答案。但如果我将内部循环更改为：

 for (int j = W; j >= wt[i]; j--)

它提供了正确的答案。我的代码有什么错误？

Answer 1

使用此代码：

 for(int i=0;i<wt.length;i++){
     for(int j=wt[i];j<=W;j++){
         dp[j]=Math.max(dp[j],val[i]+dp[j-wt[i]]);
     }
 }

发生的情况是，对于给定的

i

，

dp[j-wt[i]]

可以访问

dp

中已更改的元素 对于相同的

i

，这对应于尝试多次在背包中包含相同的项目.

向后运行

j

循环意味着

dp[j-wt[i]]

仅访问尚未受到相同

i

影响的元素，因此一个项目最多只能包含一次，这正是您所需要的。

如果您考虑使用两个数组的 0/1 背包的实现，一个数组用于 DP 表的前一行，一个数组用于现在正在计算的行，那么这可能更容易思考。您的实现是避免需要第二个数组的变体，但更新逻辑仍应产生相同的结果：新行应仅依赖于前一行，而不依赖于新行本身的其他元素。