algorithm - 给定一台重量最大的电梯和重量为 x_i 的 n 个人，找出所需的最少乘车次数

Question

input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]

output:
2  
// [[250, 175, 120], [150]]

我的初步印象是，这看起来与动态编程硬币找零/背包问题非常相似，但它不是硬币找零(这将要求最少数量的权重来获得精确数量)，而且它不是背包(重量没有值，就像我可以拥有超过 1 个背包)。

这个问题有通用名称/解决方案吗？

Answer 1

这实际上是一个(1D) Bin Packing problem :

In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem.

在这里，人物在物体和游乐设施的垃圾箱上贴图。就像装箱问题一样，我们希望尽量减少“使用”的乘车次数，并且每个人占据一定的“体积”(那个人的重量)。

如文章所述，装箱问题是 NP-hard 问题。我们可以使用动态规划(但它仍然有 - 最坏情况 - 指数时间)。

论文A New Algorithm for Optimal Bin Packing Richard E. Korf 讨论了一种算法来准确地解决这个问题。它的工作原理是首先使用启发式方法计算下限，然后使用分支定界迭代地推导出比启发式更好的解决方案，直到达到下限，或者再也找不到解决方案。