title: Solving the Integer Knapsack
body: <p>I a new to dynamic programing and have tried the integer knapsack problem here at SPOJ <a href="http://www.spoj.pl/problems/KNAPSACK/" rel="noreferrer">(http://www.spoj.pl/problems/KNAPSACK/</a>) . However, for the given test cases my solution is not giving the correct output. I'd be thankful to you if you could suggest if the following implementation by me is correct. Please note that the variable <code>back</code> is for backtracking, about which I'm not sure how to do. I hope to have your help in implementing the backtracking too. Thanks.</p>
  
  <pre><code>#include &lt;cstdio&gt;
  #include &lt;cstdlib&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;string&gt;
  #include &lt;iostream&gt;
  
  using namespace std;
  
  int knapsack(int value[], int weight[], int n, int C,
           vector &lt; int &gt;&amp;back)
  {
      int *M = new int[C + 1];
      int k;
      int i, j, tmp, pos;
      for (i = 1; i &lt;= C; i++) {
          M[i] = M[i - 1];
          pos = i - 1;
          for (j = 0; j &lt; n; j++) {
              k = i - weight[j];
              if (k &gt;= 0)
                  tmp = M[k] + value[j];
              if (tmp &gt; M[i]) {
                  M[i] = tmp;
              }
          }
          back.push_back(pos);
      }
      int ans = M[C];
      delete[]M;
      return ans;
  }
  
  
  int main()
  {
      int C, N;
      cin &gt;&gt; C &gt;&gt; N;
      int* value = new int[N+1];
      int* weight = new int[N+1];
      for ( int i = 0; i &lt;= N; i++) {
          cin&gt;&gt;value[i]&gt;&gt;weight[i];
      }
      vector &lt; int &gt;back(N, 0);
      cout&lt;&lt;knapsack(value,weight,N,C,back)&lt;&lt;endl;
      return 0;
  }
  </code></pre>
  
  <p>Here are the correct input/output test cases:</p>
  
  <pre><code>Input:
  4 5
  1 8
  2 4
  3 0
  2 5
  2 3
  
  
  Output:
  13
  </code></pre>
  
  <p>However, the output that I am getting is <code>17</code>.</p>