2

我正在尝试使用非整数值减少 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 背包算法使用 [ nx 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 中，dict 插入有一个 O(n) 更坏的情况和一个 O(1) 的“摊销”线性时间。

我错过了什么吗？

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

4

1 回答 1

0

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

因此，您会发现，在某些情况下，哈希映射可能会更好，但在常见情况下，情况正好相反。

于 2012-08-20T11:16:02.137 回答