algorithm - 贪心算法

Question

我是算法的新手，目前正在使用 you-tube 视频教程/讲座和一本书进行学习，我首先观看视频，然后阅读本书，最后尝试书中的一个问题以确保我已经了解了该主题正确。我目前正在研究贪心算法，这非常令人困惑。

书中有各种各样的问题，但我无法理解和回答一个特定的问题。

首先它给出了问题是(我刚刚复制了文本)。

有一组 n 个大小为 {x1; x2;..... xn} 和一个带有容量B。所有这些都是正整数。尝试找到这些对象的子集使得它们的总大小小于或等于B，但尽可能接近B。

所有对象都是一维的。例如，如果对象的大小为 4、7、10、12、15 和B = 20，那么我们应该选择总大小为 19 的 4 和 15(或等效地，7 和 12)。对于以下每个贪心算法，通过创建来证明它们不是最优的一个反例。尝试让你的例子尽可能糟糕，其中“糟糕”由最优解和贪心解之间的比率来衡量。因此，如果最好解值为10，贪心解值为5，则比值为2。

我该怎么做才能做到这一点？

1) 总是选择尺寸最大的物体，使得这个和所有物体的总尺寸已选择的其他对象不超过 B。对其余对象重复此操作。

Answer 1

假设问题如下:

您有一个大小为 2n 的盒子，其中一个元素的大小为 n+1，其余元素的大小为 n。

很容易看出，最优值是 2 个大小为 n 的元素，而贪心算法会得到一个大小为 n+1 的元素。

因为它对每个 n 都是真的，它实际上给了你一个期望的比率，至少使用这种贪婪的方法 2。