我是算法新手,目前正在使用 youtube 视频教程/讲座和一本书进行学习,我首先观看视频,然后阅读这本书,最后尝试书中的一个问题,以确保我正确地学习了该主题。我目前正在使用贪婪算法,这非常令人困惑。
书中有各种问题,但我无法理解和回答特定问题。
首先它给出的问题是(我刚刚复制了文本)。
有一组 n 个大小为 {x1; x2;..... xn} 和容量为 B 的 bin。所有这些都是正整数。尝试找到这些对象的子集,使它们的总大小小于或等于 B,但尽可能接近 B。
所有对象都是一维的。例如,如果对象的大小为 4、7、10、12、15 和 B = 20,那么我们应该选择总大小为 19 的 4 和 15(或等效地,7 和 12)。对于以下每个贪心算法,通过创建一个反例来证明它们不是最优的。尝试使您的示例尽可能糟糕,其中“不良”是通过最佳解决方案和贪婪解决方案之间的比率来衡量的。因此,如果最佳解决方案的值为 10,而贪心解决方案的值为 5,则比率为 2。
我该如何为以下内容执行此操作?
1) 始终选择尺寸最大的对象,以使该对象和已选择的所有其他对象的总尺寸不超过 B。对其余对象重复此操作。