algorithm - 带有哈希数组的背包 DP

Question

我正在尝试使用非整数值减少 Knapsack DP 算法所需的时间和空间。

http://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-Middle_Algorithm

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.

DP 背包算法使用 [ n x W ] 矩阵，用结果填充它，但有些列永远不会被填充 - 它们不匹配对象重量的任何组合。这样，它们最终只会在每一行中填满零，只会浪费时间和空间。

如果我们使用哈希数组而不是矩阵，我们可以减少所需的时间和空间。

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}

在 Python 中，字典插入有一个 O(n) 更坏的情况和一个 O(1)“摊销”线性时间。

我错过了什么吗？

背包 DP 算法的这种变体的复杂性是多少？

Answer 1

如果我可以这么说的话，您所说的是快乐的情况 - 在这种情况下，您可以将很少的元素放入一个体积巨大的背包中。在这种情况下，hashmap 可以证明是优化触发复杂度从 O(W * n) 到 O(min(O(2^n * n), O(W * n) ))(2^n为n个元素的组合数)。然而，通过这种估计，很明显对于元素数量不多的情况，O(2^n * n) 将主导其他估计。另外，请注意，虽然 O(W * n) 属于同一类，但后一种情况下的常数要大得多(甚至更多:第二种情况下的估计考虑了摊销的复杂性，而不是最坏的情况)。

因此您会发现，在某些情况下 HashMap 可能证明更好，但在常见情况下情况恰恰相反。