title: Knapsack DP with array of hashes
body: <p>I'm trying to reduce the time and space needed by the Knapsack DP algorithm with non-integer values. </p>
  
  <p><a href="http://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-Middle_Algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-Middle_Algorithm</a></p>
  
  <pre><code>In particular, if the [elements] are nonnegative but not integers, we could 
  still use the dynamic programming algorithm by scaling and rounding (i.e. using 
  fixed-point arithmetic), but if the problem requires  fractional digits of 
  precision to arrive at the correct answer, W will need to be scaled by 10^d,  
  and the DP algorithm will require O(W * 10^d) space and O(nW * 10^d) time.
  </code></pre>
  
  <p>The DP knapsack algorithm uses a [ n x W ] matrix, filling it up with results, but some columns never get filled - they do not match any combination of object weights. This way, they simply end up filled with zeros on each row and just waste time and space.</p>
  
  <p>If we used an array of hashes instead of a matrix, we could reduce the time and space needed.</p>
  
  <pre><code>edit:
  knapsack capacity = 2
  items: [{weight:2,value:3} ]
  
     [0   1   2]
     [0   0   0] 
  2: [0   0   3]
          ^
  Do we need this column?
  
  Substitution with hash:
  2: {0:0, 2:3}
  </code></pre>
  
  <p>In Python, dict insertion has a O(n) worse case and an O(1) "amortized" linear time.</p>
  
  <p>Am I missing something?</p>
  
  <p>What would be the complexity of such a variation on the knapsack DP algorithm ?</p>