title: Unable to figure out a bug in this knapsack code?
body: <p>I am solving a <a href="http://www.spoj.com/problems/PARTY/" rel="nofollow">this</a> spoj problem. Its been 3 days and I am unable to debug. My solution perfectly gives optimal value but it is not properly determining the items that are put in the knapsack to get the optimal value. The logic I used to store items that yield optimal solution is pretty popular but not working out for me. My code executes for the given test cases on spoj page. But fails for this particular one</p>
  
  <pre><code>7 2
  6 1
  5 1
  </code></pre>
  
  <p>My answer: 6 1
  Correct answer: 5 1</p>
  
  <p>This is the code</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;vector&gt;
  #include&lt;cstdio&gt;
  using namespace std;
  
  int max(int a, int b)
  {
      return a&gt;b?a:b;
  }
  
  
  long knapsack(int n, int wt[], int value[], int W)
  {
      int i, w, keep[n+1][W+1];
      long long dp[n+1][W+1];
      for(i=0;i&lt;=n;i++)
      {
          dp[i][0] = 0;
          keep[i][0] = 0;
      }
      for(i=1;i&lt;=W;i++)
      {
          dp[0][i] = 0;
          keep[0][i] = 0;
      }
  
      for(i=1;i&lt;=n;i++)
      {
          for(w=1;w&lt;=W;w++)
          {
              if(wt[i] &lt;= w)
                  dp[i][w] = max(value[i] + dp[i-1][w-wt[i]], dp[i-1][w]);
  
              else
                  dp[i][w] = dp[i-1][w];
          }
      }
  
     for(i=0;i&lt;=n;i++)
      {
          for(w=0;w&lt;=W;w++)
          {
              cout &lt;&lt; dp[i][w] &lt;&lt; " ";
          }
          cout &lt;&lt; "\n";
      }
  
      int k=W, sumw=0, sumv=0; i=n;
  
      while(i&gt;0 &amp;&amp; k&gt;0)
      {
          if(dp[i][k]!=dp[i-1][k])
          {
              cout &lt;&lt; "item: " &lt;&lt; i &lt;&lt; " taken " &lt;&lt; "\n";
              sumw = sumw + wt[i];
              sumv = sumv + value[i];
              k = k-wt[i];
              i = i-1;
          }
          else
              i=i-1;
      }
  
      cout &lt;&lt; sumw &lt;&lt; " " &lt;&lt; sumv &lt;&lt; "\n";
  
  
  
  }
  
  int main()
  {
      int items, i, W;
      cin &gt;&gt; W;
      cin &gt;&gt; items;
      while(W!=0 &amp;&amp; items!=0)
      {
          int wt[items+1], value[items+1];
          for(i=1; i&lt;=items; i++)
              cin &gt;&gt; wt[i] &gt;&gt; value[i];
          knapsack(items, wt, value, W);
          cin &gt;&gt; W &gt;&gt; items;
  
      }
  }
  </code></pre>
  
  <p>Please help me debug if you got any ideas? Thanks so much!</p>
  
  <p>PS: There are many spoj users with an exact same bug because of which they are getting WA, as seen in the comments. </p>