Ist das 0-1-Rucksack-Problem, bei dem Wert gleich Gewicht NP-Complete?

Question

Ich habe ein Problem, von dem ich vermute, dass es NP-Complete ist. Es ist leicht zu beweisen, dass es NP ist. Mein aktueller Gedankenzug dreht sich um die Verwendung einer Reduzierung des Rucksacks, aber es würde zu einem 0-1-Knapsack führen, wobei der Wert jedes Elements seinem Gewicht entspricht.

Ist das noch NP-Complete? Oder vermisst ich etwas?

Answer 1

Ja, das nennt man die Subset-Sum-Problem und ist np-hard.