我有一些二进制位，具有不同的能力，并与指定大小某些对象。 我们的目标是在收拾垃圾箱这些对象。 到现在为止它类似于装箱问题。 但扭转是，每个对象具有与另一部分重叠。 因此，尽管对象1和2具有尺寸S1和S2，当我把它们放在同一个箱子装满空间小于S1 + S2。 假设我知道这个重叠度为每对对象，有没有像那些原创装箱对于这个问题太任何近似算法？
Answer 1:
答案是用一种树的捕获假设对象可以被打破的物体的相似性。 然后运行一个贪心算法根据树填补了垃圾箱。 该算法结合3-X逼近。 但是，也应该有更好的答案。
该方法呈现在迈克尔辛德拉，拉梅什K. Sitaraman，PRASHANT J.谢诺伊：虚拟机共享托管感知算法。 SPAA 2011：367-378 。
我得到了这样的回答这个线程 ，但只是想通过给答案关闭了这个问题。
Answer 2:
唯一的算法我想会的工作是修剪不适合入箱，并使用另一二进制位的项目。 我的意思不是首次适应算法，但要等待一段时间，然后使用新的箱的物品。 在现实中，你可以只使用另一二进制位？ 这是一个实用的方法。 我的意思是，你可以在这个例子中成长的bin向左或向右，如： http://codeincomplete.com/posts/2011/5/7/bin_packing/ 。
文章来源: bin packing with overlapping objects
