title: Knapsack algorithm for two bags
body: <p>I've found <a href="https://stackoverflow.com/questions/14786941/optimal-way-of-filling-2-knapsacks">thread</a> which provides pseudo-code for knapsack algorithm with 2 knapsacks. 
  I've tried implement it in C++, but it doesn't work as suppose. Here's code:</p>
  
  <pre><code>#include &lt;cstdio&gt;
  #define MAX_W1 501
  #define MAX_W2 501
  
  int maximum(int a, int b, int c) {
      int max = a&gt;b?a:b;
      return c&gt;max?c:max;
  }
  
  int knapsack[MAX_W1][MAX_W2] = {0};
  
  int main() {
      int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost
  
      scanf("%d %d %d", &amp;n, &amp;s1, &amp;s2);
  
      // filing knapsack
      for (int i = 0; i &lt; n; i++) {
          scanf("%d %d", &amp;gain, &amp;weight);
  
          for (int w1 = s1; w1 &gt;= weight; w1--) {
              for (int w2 = s2; w2 &gt;= weight; w2--) {
                  knapsack[w1][w2] = maximum(
                      knapsack[w1][w2],                 // we have best option
                      knapsack[w1 - weight][w2] + gain, // put into sack one
                      knapsack[w1][w2 - weight] + gain  // put into sack two
                  );
              }
          }
      }
  
      int result = 0;
  
      // searching for result
      for (int i = 0; i &lt;= s1; i++) {
          for (int j = 0; j &lt;= s2; j++) {
              if (knapsack[i][j] &gt; result) {
                  result = knapsack[i][j];
              }
          }
      }
  
      printf("%d\n", result);
  
      return 0;
  }
  </code></pre>
  
  <p>For instance for following input:</p>
  
  <pre><code>5 4 3
  6 2
  3 2
  4 1
  2 1
  1 1
  </code></pre>
  
  <p>I have output:</p>
  
  <pre><code>13
  </code></pre>
  
  <p>Obviously it's wrong because I can take all items (1,2 into first bag and rest to second bag) and sum is 16.
  I would be grateful for any explanation where I get pseudo-code wrong.</p>
  
  <p><strong>I made little update since, some people have problem with understanding the input format:</strong></p>
  
  <ol>
  <li>First line contains 3 numbers as follows number of items, capacity of sack one, capacity of sack two</li>
  <li>Later on there are n lines where each contains 2 numbers: gain, cost of i-th item.</li>
  <li>Assume that sacks cannot be larger than 500.</li>
  </ol>