重み付けサブセットの同時最小化と最大化のNP硬度の証明

Question

次の

として定義されている問題に取り組んでいます

$ n $ の集合 $ r \ subseteq \ mathbb {n} \ times \ mathbb { $ と数字 $ z、g \ mathbb {n} $ 、 $ z $ は私達のリソースの尺度であり、 $ g $ は私達の必要最小限の報酬です、セット $ rがあります'\ subseteq r $ 、そのため、 $ \ sum _ {（z、g）}} z \ leq z $ と $ \ sum _ {（z、g）\ in r '} g \ geq g $ ？

私はそのNP完全性を見せて、すでにNPにあることを示しています。私はNP硬さに苦しんでいます。私の既知のNPハードの問題は、SAT、3SAT、パーティション、サブセット合計とBINパッキングです。

私の闘いは、2つの異なる価値観、コストと報酬のバランスをとる必要があるという事実に主に思われます。これは私が言及した設定された関連の問題のいずれかではそうではなく、私はSATまたは3SATでこれをモデル化する方法を考えることができません。私はここで何を見逃していますか？ NP硬さを表示する方法およびこれらの問題のみを使用してこの問題のNP完全性を示す方法は？

Answer 1

これは私にとってナップザック問題

• $ z $ は、各項目の重みです。
• $ Z $ は、ナップザックの容量です。
• $ g $ 項目の値、
• $ G $ 達成される値。

問題は np-complete ですが、動的プログラミングを使用して、擬似多項式 $ O（n \ cdot w）$ ここで、 $ w=max _ {（z、g）\ in r}（g）$ 。

サブセット合計問題のサブセット合計の問題を減らすことで、ナップザック問題がNP完了であることを証明できます。 >。実際、サブセット合計は、 $ z= g $ の特別なケースです。各問題の「重み」は、その「値」と同じです。