Fre*_*red 0 algorithm knapsack-problem
我正在寻找一个案例,其中贪婪算法选择具有重量<最大重量并且首先放入背包的最高值/重量比的物品将不起作用.有没有人有例子？因为否则,贪婪的最坏情况将是O(nlogn)(nlogn以降序值/权重排序,n来经历它),而动态编程方式的最坏情况是O(nW),使logn <时贪婪更快W.
考虑一个容量为4的背包,以及具有以下重量和值的物品:
Item Weight Value value/Weight A 3 1.65 0.55 B 2 1 0.5 C 2 1 0.5
基于每重量值的贪婪算法首先选择项目A然后退出,剩余的容量不足以用于任何其他项目 - 总值1.65.然而,最佳解决方案是选择项目B和C,它们共同占据全部容量并且具有2的组合值.
更一般地说,贪婪算法在选择一组不占用整个可用容量的项目时可能会失败.填充更多可用容量的不同项目有时是更好的选择.