input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]
output:
2
// [[250, 175, 120], [150]]
我最初的印象是,这看上去与动态编程的找零/背负问题非常相似,但是它不是找零(这将要求最少的砝码数量才能准确确定重量),也不是背负零钱包(即砝码没有值,就像我可以装多个背包。
这个问题有通用的名称/解决方案吗?
最佳答案
这实际上是一个(1D) Bin Packing problem:
在此,人员将物体映射到游乐设施上的垃圾箱中。像垃圾箱包装问题一样,我们要尽量减少“使用”的乘车次数,并且每个人都占据一定的“体积”(该人的体重)。
如文章中所述,垃圾箱包装问题是NP-hard。我们可以使用动态编程(但它仍然具有-最坏的情况-指数时间)。
理查德·科夫(Richard E. Korf)的A New Algorithm for Optimal Bin Packing论文讨论了一种精确解决该问题的算法。它的工作方式是先使用启发式方法并计算下界,然后使用branch and bound迭代地得出比启发式方法更好的解决方案,直到达到下界,或者找不到解决方案为止。