贪心算法在0-1背包问题中失败的情况

Question

贪心算法在0-1背包问题中失败的情况

3

我正在寻找一种情况，即选择价值/重量比最高的物品贪心算法，当其重量 < 最大重量时将其放入背包中，这种算法不起作用。有人有例子吗？否则，贪婪算法的最坏情况为O（nlogn）（nlogn为值/重量的降序排序时间，n为遍历时间），而动态规划的最坏情况为O（nW）。当 logn < W 时，贪心算法更快。

- Fred

你已经想过一种方法了吗？ - hugomg

2个回答

1

我们还可以将贪心算法无法给出全局最优解的情况进行概括。

具体如下：

weights = {1，x，x+1}

目标重量 = z

x是z的倍数
y小于z且大于x
同时x和y都大于1
包含1以便在所有贪心方法中都有解决方案

对于上述一般情况，大多数情况下贪心方法都会失败。您可以尝试一些例子。

- Mehant Kammakomati

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

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

- John Bollinger · Accepted Answer

考虑一个容量为4的背包，以及以下重量和价值的物品：

物品  重量  价值  单位重量价值
 A    3     1.65    0.55
 B    2     1       0.5
 C    2     1       0.5

基于单位重量价值的贪心算法会先选择物品A, 然后停止，因为没有足够的容量来放置其他物品--总价值为1.65。然而，最优解是选择物品B和C，它们共同占用了全部容量并具有2的组合价值。

更一般地说，当贪心算法选择的物品集不占用整个可用容量时，会失败。填满更多可用容量的不同物品集有时是更好的选择。