带有重叠物体的垃圾箱包装 [英] bin packing with overlapping objects
问题描述
我有一些具有不同容量的垃圾箱和一些具有指定大小的物体.目标是将这些对象包装在垃圾箱中.到目前为止，它类似于垃圾箱包装问题.但是，不同之处在于，每个对象之间都存在部分重叠.因此，虽然对象1和2的大小分别为s1和s2，但是当我将它们放在同一容器中时，填充空间小于s1 + s2.假设我知道每个对象对都有这个重叠值，那么是否也有类似的近似算法，例如用于此问题的原始装箱算法?
I have some bins with different capacities and some objects with specified size. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object has a partial overlap with another. So while object 1 and 2 has sizes s1 and s2, when I put them in the same bin the filled space is less than s1+s2. Supposing that I know this overlapping value for each pair of objects, is there any approximation algorithm like the ones for original bin-packing for this problem too?
推荐答案
答案是使用一种树，假定对象可以被破坏，该树捕获对象的相似性.然后运行贪婪算法以根据树填充垃圾箱.该算法具有3-x近似界限.但是，也应该有更好的答案.
The answer is to use a kind of tree that captures the similarity of objects assuming that objects can be broken. Then run a greedy algorithm to fill the bins according to the tree. This algorithm has 3-x approximation bound. However, there should also be better answers.
此方法在
我从此线程得到了这个答案，但我只是想关闭它通过给出答案来提问.
I got this answer from this thread but just wanted to close this question by giving the answer.
这篇关于带有重叠物体的垃圾箱包装的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
