Ist das 0-1-Rucksackproblem, bei dem der Wert gleich dem Gewicht NP-vollständig ist?

9

Ich habe ein Problem, von dem ich vermute, dass es NP-vollständig ist. Es ist leicht zu beweisen, dass es NP ist. Mein aktueller Gedankengang dreht sich um die Verwendung einer Reduzierung des Rucksacks, aber es würde zu Instanzen von 0-1-Rucksack führen, wobei der Wert jedes Gegenstands gleich seinem Gewicht ist.

Ist das noch NP-vollständig? Oder fehlt mir etwas?

complexity-theory np-complete decision-problem packing Zeta Zwei
quelle
Dies ist Jahre zu spät, aber trotzdem: Ihre Formulierung deutet darauf hin, dass Sie möglicherweise versuchen, in die falsche Richtung zu reduzieren. Sie müssen vom Rucksack auf Ihr Problem reduzieren , was bedeutet, dass Sie beliebige Rucksackinstanzen zulassen müssen (die möglicherweise Instanzen Ihres Problems mit einer speziellen Struktur erzeugen ) - kein Teil dieser Prozedur würde zu Rucksackinstanzen mit einer speziellen Struktur "führen" Struktur. (OTOH, es ist sinnvoll zu fragen, ob ein Sonderfall von Knapsack noch NP-vollständig ist, da es möglicherweise einfacher ist, ihn zu reduzieren.)
j_random_hacker
Ja. Was ich meinte war, dass ich vom Rucksack reduziere, aber speziell vom "0-1-Rucksack, wobei der Wert jedes Gegenstands gleich seinem Gewicht ist". Es war also nur meine Formulierung, die ein wenig abweicht.
Zeta zwei

Antworten:

8

Ja, dies wird als Teilmengenproblem bezeichnet und ist NP-hart.

Aryabhata
quelle
Vielen Dank! Ich habe gerade festgestellt, dass ich diese Entdeckung früher gemacht habe. Leider habe ich auch festgestellt, dass meine Ermäßigung überhaupt nicht funktioniert hat. Zurück zum Zeichenbrett. :(
Zeta zwei
@ ZetaTwo: Gern geschehen :-)
Aryabhata