1

我是算法新手,目前正在使用 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。对其余对象重复此操作。

4

2 回答 2

1

假设以下问题实例:

你有一个大小的盒子2n,一个大小的元素,n+1其余的都是大小n

很容易看出,最优的是 2 个大小元素n,而贪婪者会得到一个大小元素n+1

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

于 2012-03-06T18:18:26.257 回答
0

这听起来类似于 0-1 背包问题,其中每个项目的大小不同但值相同,这意味着任何一个项目除了其大小外,没有任何偏好放入垃圾箱。在您的代码中,您需要检查每个项目并计算导致的最大总大小,无论是否将其放入垃圾箱而不超过垃圾箱的容量。

于 2017-04-19T12:45:09.720 回答