Retrieving a List of Selected Items in a Knapsack DP Matrix

Question

I tried to implement stack overflow Response . But it does not work.

TEST CASE:

   int val[] = {10,40,30,50};
   int wt[] = {5,4,6,3};
     W = 10;

OUTPUT KNAPSACK DP MATRIX:

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 5 5 5 5 5 5 
0 0 0 0 4 5 5 5 5 9 9 
0 0 0 0 4 5 6 6 6 9 10 
0 0 0 3 4 5 6 7 8 9 10 

Wt, which can be achieved, is: 10

sum wt of the selected elements: 11 (which should be incorrect only 10)

selected → 6 (3rd element) and 5 (1st element) [this is not true]

int knapSack(int W, int wt[], int val[], int n)
{
 int i, w;
 int K[n+1][W+1]; 
  int picks[n+1][W+1] = {0};
  // Build table K[][] in bottom up manner
  for (i = 0; i <= n; i++)
   {
   for (w = 0; w <= W; w++)
   {
       if (i==0 || w==0)
           K[i][w] = 0;
       else if (wt[i-1] <= w){
          //val[i-1 ] is value of curr i
             K[i][w] = max(wt[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
             if (val[i-1]+K[i-1][w-wt[i-1]] > K[i-1][w]){
                picks[i][w]=1;
             }
            else
                picks[i][w]=-1;
       }
       else{
        // wt of individual is > limit 
             picks[i][w] = -1; 
             K[i][w] = K[i-1][w];
    }
   }
  }
}

To print selected items I use

while (w > 0 && i > 0 ){

if ((K[i][w] - K[i-1][w-wt[i-1]]) == wt[i-1]){
    weight += wt[i-1];
    i = i - 1;
    w = w - wt[i-1];
}
else{
  i = i - 1;
}

}

Answer 1

 w =  w - wt[i-1] 

in fact

w =  w - wt[i-2] 

since i = i - 1 is calculated before it. Below the code below will work.

    weight += wt[i-1];
    i = i - 1;
    w = w - wt[i] ;