The code for 0/1 Knapsack Problem is not working

Question

This is the code I used:

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];
         
    } 
}

It is giving the wrong answer for this code. But if I change the inner loop to :

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

It is providing the correct answer. what is the error in my code?

Answer 1

With this code:

 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]]);
     }
 }

What happens is that for a given i, dp[j-wt[i]] can access an element of dp that was already changed for the same i, which corresponds to trying to include the same item in the knapsack multiple times.

Running the j-loop backwards means that dp[j-wt[i]] only accesses elements that haven't been affected for the same i yet, so an item can only be included at most once, which is what you need.

This may be easier to think about if you consider the implementation of 0/1 knapsack that uses two arrays, one array for the previous row of DP tableau and one array for the row that is being computed now. Your implementation is a variant of that which avoids the need for a second array, but the update logic should still produce the same results: the new row should depend only on the previous row, but not on other elements of the new row itself.