algorithm - 贪心算法失败 0-1 背包 p‌r‌o‌b‌l‌e‌m 的情况

Question

我正在寻找一种情况，其中贪婪算法会选择重量小于最大重量的最高值(value)/重量比的元素并将其首先放入背包中。有人有例子吗？因为否则，贪婪的最坏情况将是 O(nlogn)(nlogn 按降序值/权重排序，n 遍历它)而动态编程方式的最坏情况将是 O(nW)，当 logn <

Answer 1

考虑一个容量为 4 的背包，以及具有以下重量和值(value)的元素:

Item  Weight  Value  value/Weight
 A      3      1.65     0.55
 B      2      1        0.5
 C      2      1        0.5

基于每重量值(value)的贪婪算法会首先选择项目 A，然后退出，因为没有足够的容量留给任何其他项目——总值(value) 1.65。然而，最佳解决方案是选择项目 B 和 C，它们一起恰好占据了全部容量并且组合值为 2。

更一般地说，当贪婪算法选择了一组未占用全部可用容量的项目时，它可能会失败。填充更多可用容量的一组不同的项目有时是更好的选择。