0-1繰り返しのナップザック

Question

私の質問は、ナップザック問題のO（NW）が疑似多項式である理由です。

スタックオーバーフローでの説明をたくさん読みましたが、実際にはわかりません。 （ https://stackoverflow.com/questions. / 19647658 / is-is-is-sud-is-is-how-dos-IT - 多項式-Time https://stackoverflow.com/questions/4538581/Why- IS-THE-KNAPSACK問題 - 疑似多項式＃応答-4538668 ）

コアのことは、「W」と「W」の入力を「Logw」の入力として「N」として「N」として考えなければならない理由です。

多くの説明は、 'w'が整数であるが「n」は単なるアイテムの数であると述べた。したがって、 'W'サイズのみが「logw」に比例します。

私はこの論理が 'n'に適用されなければならないと思います。

アイテムを区別するために、1からNの項目に番号を付けていると仮定して、

1からnまでの数字を数える必要があります。

ループがW回の反復を行うことが同じだと思います。

だから私はそれが 'w'と同じだと思います。このカウントでも 'log n'ビットが必要です。

この問題を誤解するのは何ですか？

ありがとう。

Answer 1

入力の入力方法：

• 項目1の重さと値。
• 項目2の重さと値。
• ...
• 項目の重みと値 $ n $ 。
• $ w $ 。

重量と値が整数であるとします。 $ w $ 。その後、エンコードの長さ $$ \ omega（n + \ log w）、o（n \ log m + \ log w）。 $$ うまくいけば、これは $ n $ と $ w $ の違いを明確にしています。