sol*_*ire 5 algorithm packing bin-packing branch-and-bound
我正在寻找一种能够以最有效的方式解决我的问题的算法.
问题描述:
我有一个项目列表(只允许正整数)和相同容量的固定数量的箱子.到目前为止,我考虑过分支定界算法,但我不确定它是否是这种情况下的最佳方法.
例:
给出一个项目列表:
(3, 4, 4, 2, 3, 9, 2)
还有三个容量为9的容器,我需要将它们包装起来:(物品的顺序无关紧要)
[3, 4, 2], [4, 3, 2], [9]
我认为这是bin-packing问题的变种(我知道它是NP-complete),但是由于我不是想尽量减少使用的bin数量,我想知道是否有更好的解决方案.
这是多箱包装问题：
\n\n\n\n\n给定一组项目，每个项目都有特定的大小，以及一组垃圾箱，每个\n都有特定的大小\xe2\x80\x93，是否存在将项目分配到垃圾箱的\n，使得没有项目被拆包并且没有超出垃圾箱容量？
\n
一般来说，它是NP困难的。然而，有几种特殊情况可以有效地解决，无论是近似的还是最佳的。
\n\n参见Wolfgang Stille aus G\xc3\xb6ppingen\ 的论文
\n