title: Knapsack algorithm with 2 properties. How to implement that in a 3d array?
body: <p>I'm having a problem with understanding knapsack problem when there's more than 1 property.
  When there's 1 property, </p>
  
  <p>I have to write a program that uses knapsack algorithm with a 2 properties. Teacher told us, It has to be done in a 3d array. Wrong implementation will lead to O(2^n) processing time. I can't imagine how would such array look like.</p>
  
  <p>Let's say here's my input:</p>
  
  <pre><code>4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
  1 1 1 // 1st property, 2nd property, cost
  1 2 2 // 1st property, 2nd property, cost
  2 3 3 // 1st property, 2nd property, cost
  3 4 5 // 1st property, 2nd property, cost
  </code></pre>
  
  <p>And the output would look like that:</p>
  
  <pre><code>4    // the cheapest sum of costs of 2 records
  1 3  // numbers of these 2 records
  </code></pre>
  
  <p>The explanation of output:
  2 sets of records fit's into 1'st line of input:</p>
  
  <p>(1) - record number 1 and record number 3</p>
  
  <pre><code>  1 1 1
  + 2 3 3
  -------
    3 4 4
  </code></pre>
  
  <p>(2) - record number 4</p>
  
  <pre><code>  3 4 5
  </code></pre>
  
  <p>Because 1st set of the records is the cheapest (4 &lt; 5), we chose it. Not only I'll have to find out whether such set of records exists, I'll also have to find records I've summed.</p>
  
  <p>But for now, I only need to understand, how will 3d array look like. Could some of You help me out with that and show, layer by layer, just like in my image, how would this look like?
  Thanks.</p>