0-1ナップサックの問題は、値が重量np完全に等しい場合ですか？

Question

NPコンプリートだと思う問題があります。それがNPであることを証明するのは簡単です。私の現在の思考の列は、ナップサックからの削減を使用して展開していますが、それにより、すべてのアイテムの値がその重量に等しい0-1ナプサックのインスタンスが発生します。

これはまだnp完全ですか？それとも私は何かが足りませんか？

Answer 1

はい、これはと呼ばれます サブセットサムの問題 そして、NPハードです。