每个物品重量相同的0-1背包问题是否为NP完全问题？

Question

每个物品重量相同的0-1背包问题是否为NP完全问题？

3

0-1背包问题被认为是NP完全问题。但如果每个物品的重量相同，该问题仍然是NP完全问题吗？

- wzb5210

想象一下在暗黑破坏神（或你最喜欢的类似游戏）中的一个物品储存箱，你可以将战利品放入其中。如果所有物品占用一个“格子”（或者“重量为1”），那么如何安排才能只保留“最好的东西”（例如最贵重的东西）？你如何知道哪些东西不应该放入储存箱？由于没有重量/大小限制，2D储存箱可以简化为1D腰带。 - user166390

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Running Wild · Accepted Answer

不行，因为你总是只拿最有价值的物品。