0/1背包问题代码异常：正向遍历内循环为何出错？

我编写了一段解决0/1背包问题的Java代码，当内循环采用从物品重量到背包容量W的正向遍历时，输出结果错误；但将内循环改为从W倒序遍历至物品重量后，结果正确。请问原代码的错误原因是什么？

错误代码（正向内循环） #

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

错误原因分析 #

• 0/1背包的核心规则是每个物品只能被选择一次，你使用的是一维DP数组优化空间的实现方式。
• 当内循环正向遍历时，dp[j-wt[i]]会是当前物品i被处理过之后的更新值。比如在遍历j的过程中，先处理了较小的j值，此时dp[j]已经包含了选物品i的状态；当后续处理更大的j时，j-wt[i]对应的就是已经选过物品i的状态，这就导致同一个物品被多次选取，逻辑变成了允许物品重复选的完全背包，违背了0/1背包的要求。
• 当内循环倒序遍历时，dp[j-wt[i]]保留的是还没处理物品i时的原始状态，也就是没有选过物品i的DP值。这样在更新dp[j]时，只会用一次当前物品i的价值和重量，保证了每个物品最多被选一次，符合0/1背包的约束。

内容的提问来源于stack exchange，提问作者ammu