CS 6.006 Lecture 21 DP III: Parenthesization, Edit Distance, Knapsack を見る

わかったこと

文字列系のDPでよく使われるsub-problem

• prefix
• suffix
• substring

当然といわれれば当然。prefixとsuffixをどちらも使いそうな時はつまりsubstringである。

pseudo polynomial

ナップザック問題：

ナップザックに、重さ、価値の品物を入れるか入れないか選ぶ。 品物が全部でN個、ナップザックに入れられる重さは最大Wまでのとき、価値の最大値は？

という問題。重さをSとして、以下のような漸化式を使って解く場合を考える。

時間計算量は、である。これは、(inputに関して)polynomial-timeではない。 Sが非常に大きい場合があるからである。

講義では、「SがWordに収まらない場合」と表現されている。 Wordとは、複数のバイトをまとめたデータ単位である。 コンピュータの実装によって異なるらしいが、1ワード = 2バイト(= 16ビット)だろうか？ つまり、-2¹⁵から2¹⁵ - 1までの数である。(smallint)

SがWordに収まらない場合、入力のサイズはO(nlogS)であるらしい。 S = exp(logS)なので、入力に関して指数時間かかってしまう。よってこのときはpolynomial-timeではないらしい。 入力のサイズがO(nlogS)である理由がよくわからないので調べる必要がある。