Beweis für NP-Härte der gleichzeitigen Minimierung und Maximierung einer gewichteten Teilmenge

Question

Ich arbeite an einem Problem, das als Folgendes definiert ist

Angesichts eines Satzes von $ n $ Elemente namens $ R \ Subseteq \ MathBB {n} \ times \ mathbb { N} $ und -nummern $ z, g \ in \ mathbb {n} $ , wobei $ Z $ ist ein Maß für unsere Ressourcen und $ g $ ist unsere notwendige minimale Belohnung, gibt es einen Set $ r '\ subseteq r $ , so dass $ \ sum _ {(z, g) \ in r'} z \ leq z $ und $ \ Sum _ {(z, g) \ in R '} g \ geq g $

Ich möchte seine NP-Vollständigkeit zeigen und haben gezeigt, dass es bereits in NP ist. Ich kämpfe mit der NP-Härte. Meine bekannten NP-Hard-Probleme sind die SAT-, 3SAT-, Partitions-, Subset-Summe und das Bin-Verpackung.

Mein Kampf scheint meistens mit der Tatsache zu sein, dass wir jetzt zwei verschiedene Werte ausbalancieren müssen, die Kosten und die Belohnung. Dies ist in keiner der eingestellten, in einem der festgelegten festgelegten Probleme der Fall, und ich kann nicht daran denken, wie man dies in SAT oder 3sat modelliert. Was vermisse ich hier? Wie kann ich die NP-Härte zeigen und als solche NP-Vollständigkeit dieses Problems nur mit diesen gegebenen Problemen verwenden?

Answer 1

Das klingt für mich wie die Rucksackproblem wo

.
• $ Z $ ist das weight von jedem Artikel,
• $ Z $ ist die -Kapazität des rucksacks,
• $ g $ der Wert des Elements und
• $ g $ der zu erreichende Wert.

Das Problem ist np-komplett , aber lösbar, mit dynamischer Programmierung, in pseudo-polynom-zeit $ o (n \ cdot w) $ wo $ w= max _ {(z, g) \ in r} (g) $ .

Sie können nachweisen, dass das Rucksack-Problem NP-komplett ist, indem er von der Subset-Summenprobleme senkt . In der Tat ist die Subset-Summe ein Sonderfall von Knapsack, in dem $ Z= G $ ; Das "Gewicht" jedes Problems ist derselbe wie sein "Wert".