[解決済み] なぜナップザック問題は擬似多項式なのか？

疑問点

私は、以下のことを知っています。 Knapsack がNP完全であることは知っているが、DPで解くことができる。彼らはDP解は pseudo-polynomial であり、それは入力の長さ(すなわち、入力を符号化するのに必要なビット数)の指数関数であるからです。残念ながら、私はそれを理解できませんでした。どなたか、次のように説明してください。 pseudo-polynomial のことをゆっくり説明してくれませんか？

どのように解決するのですか？

実行時間は、N 個のアイテムとサイズ W のナップザックからなる無限のナップザック問題に対して O(NW) です。しかし W は入力の長さの多項式ではないので、これは 擬似 -多項式となります。

W = 1,000,000,000を考えてみましょう。この数を表現するのに必要なのは40ビットだけなので、入力サイズ＝40ですが、計算実行時間は1,000,000,000の倍数を使うので、O(2) ⁴⁰ ).

ですから、実行時間はより正確に言うと、O(N.2 ^{ビットで、W} という指数関数的なものです。

も参照してください。

• ナップザック問題がNP完全であることを理解するには？
• ナップサックのNP完全性
• 0-1ナップザック問題に対する動的計画法アルゴリズムの複雑さ
• 擬似多項式時間