我正在寻找能够以最有效的方式解决我的问题的算法。
问题描述:
我有一个项目列表(只允许使用正整数)和固定数量的相同容量的箱子。到目前为止,我考虑过分支定界算法,但我不太确定在这种情况下它是否是最佳方法。
示例:
给定一个项目列表:
(3, 4, 4, 2, 3, 9, 2)
和三个容量为9的箱子 我需要这样包装它们:(元素的顺序无关紧要)
[3, 4, 2], [4, 3, 2], [9]
我认为这是装箱问题的一个变体(我知道它是 NP-complete),但由于我不是要尽量减少使用的箱子数量,我想知道是否有更好的解决方案。
最佳答案
这是多箱装箱问题:
Given a set of items, each of a specific size, and a set of bins, each of a specific size as well – is there a distribution of items to bins such that no item is left unpacked and no bin capacity is exceeded?
一般来说它是 NP-hard。但是,有几种特殊情况可以近似甚至最优地有效解决。
关于algorithm - 将元素包装到固定数量的箱子中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8023113/