こんにちはみんな質問があります。誰かがそれを証明する方法を知っているかどうか疑問に思います。
ここに質問があります：サブセット和問題はNP完全であることが示されています。入力は、正の数w1、...、wn、Wのシーケンスです。ここで、Wはターゲットの重みです。問題は、いくつかの重みの合計が目標の重みに等しくなるように、重みのセットF⊆{1、...、n}があるかどうかを判断することです（つまり、w1 + ... + wi = W）
。制限付きサブセット和問題はサブセット和のように定義されますが、ターゲットの重みがすべての重みの合計の半分未満であるという追加の要件があります。（これが失敗した場合、入力はすぐに拒否される必要があります。）制限付きサブセット和がNP完全であることを示します。
ありがとうございました。