0-1背包问题是否等于重量np complete？

Question

我有一个问题，我怀疑是NP完整的。很容易证明它是NP。我目前的思想列车围绕着使用背包的减少旋转，但这将导致0-1 knapsack的实例，每个项目的价值等于其重量。

这仍然是NP完成吗？还是我想念什么？

Answer 1

是的，这称为 子集问题 并且是NP-HARD。