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 は最適化であることが証明され、複雑さが(は n 要素の組み合わせの数)からO(W * n)単純にトリガーされます。ただし、この推定では、要素の数がそれほど多くない場合、が他の推定を支配することは明らかです。また、これらは同じクラスですが、後者の場合の定数はかなり大きいことに注意してください(さらに、2 番目のケースの推定では、最悪のケースではなく、償却後の複雑性が考慮されます)。O(min(O(2^n * n), O(W * n)))2^nO(2^n * n)O(W * n)

したがって、特定のケースではハッシュ マップの方が優れていることがわかりますが、一般的なケースでは逆のことが当てはまります。

于 2012-08-20T11:16:02.137 に答える