title: Getting list of selected items in Knapsack DP matrix
body: <p>I have tried implementing stack Overflow <a href="https://stackoverflow.com/questions/7489398/how-to-find-which-elements-are-in-the-bag-using-knapsack-algorithm-and-not-onl">Answered Solution</a>. But it is not working.</p>
  
  <p><strong>TEST CASE :</strong> </p>
  
  <pre><code>   int val[] = {10,40,30,50};
     int wt[] = {5,4,6,3};
       W = 10;
  </code></pre>
  
  <p><strong>OUTPUT KNAPSACK DP MATRIX:</strong> </p>
  
  <pre><code>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 
  </code></pre>
  
  <blockquote>
    <p>Wt that can be reached is  : 10 </p>
    
    <p>sum of wt of selected items : 11 <strong>(which is wrong should be only 10)</strong></p>
    
    <p>selected -> 6 (3rd item) and 5 (1st item) <strong>[which is wrong]</strong></p>
  </blockquote>
  
  <pre><code>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 &lt;= n; i++)
     {
     for (w = 0; w &lt;= W; w++)
     {
         if (i==0 || w==0)
             K[i][w] = 0;
         else if (wt[i-1] &lt;= 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]] &gt; K[i-1][w]){
                  picks[i][w]=1;
               }
              else
                  picks[i][w]=-1;
         }
         else{
          // wt of individual is &gt; limit 
               picks[i][w] = -1; 
               K[i][w] = K[i-1][w];
      }
     }
    }
  }
  </code></pre>
  
  <p>For printing the picked elements , I am using </p>
  
  <pre><code>while (w &gt; 0 &amp;&amp; i &gt; 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;
  }
  
  }
  </code></pre>