标签列表
每个物品重量相同的0-1背包问题是否为NP完全问题?
algorithm
np-complete
np
3
3
0-1背包问题被认为是NP完全问题。但如果每个物品的重量相同,该问题仍然是NP完全问题吗?
-
wzb5210
1
想象一下在暗黑破坏神(或你最喜欢的类似游戏)中的一个物品储存箱,你可以将战利品放入其中。如果
所有物品占用一个“格子”
(或者“重量为1”),那么如何安排才能只保留“最好的东西”(例如最贵重的东西)?你如何知道哪些东西
不应该
放入储存箱?由于
没有重量/大小限制
,2D储存箱可以简化为1D腰带。
- user166390
1
个回答
2
2
不行,因为你总是只拿最有价值的物品。
-
Running Wild
1
你如何证明这是最优的?
- LucG
回答链接
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接
相关问题
5
所有的NP问题都是NP完全问题吗?
9
布尔表达式的最小化是否为NP完全问题?
4
0-1多维背包问题
5
子集推断问题是否是NP完全问题?
4
背包问题:带有重量和物品限制
3
背包问题0-1路径重构(选择哪些物品)
4
有限背包问题(Constrained Knapsack)但不考虑物品重量
4
生成所有字符串排列是否为NP完全问题?
6
这个问题是否为 NP 完全问题?
7
背包问题(仅考虑物品重量)