我有一些容量不同的垃圾箱和一些指定大小的对象。目标是将这些对象打包到垃圾箱中。到目前为止，它类似于装箱问题。但扭曲的是，每个对象都与另一个对象有部分重叠。因此，虽然对象 1 和 2 的大小分别为 s1 和 s2，但当我将它们放在同一个 bin 中时，填充的空间小于 s1+s2。假设我知道每对对象的重叠值，是否也有任何近似算法，例如用于该问题的原始装箱算法？
问问题
909 次
2 回答
2
答案是使用一种树来捕获对象的相似性，假设对象可以被破坏。然后运行一个贪心算法来根据树填充垃圾箱。该算法具有 3-x 近似界。但是，也应该有更好的答案。
此方法在 Michael Sindelar、Ramesh K. Sitaraman、Prashant J. Shenoy：虚拟机托管共享感知算法中介绍。SPAA 2011：367-378。
我从这个线程得到了这个答案，但只是想通过给出答案来结束这个问题。
于 2012-08-07T22:50:36.583 回答
0
我认为唯一可行的算法是修剪不适合放入垃圾箱的物品并使用另一个垃圾箱。我不是指第一次拟合算法，而是等待一段时间，然后为项目使用新的垃圾箱。实际上，您可以只使用另一个垃圾箱吗？这是一种实用的方法。我的意思是你可以像这个例子一样向左或向右增长垃圾箱：http: //codeincomplete.com/posts/2011/5/7/bin_packing/。
于 2012-07-25T12:04:18.827 回答