我是算法的新手，目前正在使用 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。对其余对象重复此操作。
最佳答案
假设问题如下:
您有一个大小为 2n 的盒子，其中一个元素的大小为 n+1，其余元素的大小为 n。
很容易看出，最优值是 2 个大小为 n 的元素，而贪心算法会得到一个大小为 n+1 的元素。
因为它对每个 n 都是真的，它实际上给了你一个期望的比率，至少使用这种贪婪的方法 2。
关于algorithm - 贪心算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9589439/