给定一个最大重量的电梯和 n 个体重 x_i 的人，找出所需的最少乘车次数
Given an elevator with max weight and n people with x_i weights, find out minimum number of rides needed
input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]
output:
2
// [[250, 175, 120], [150]]
我的初步印象是，这看起来与动态规划硬币问题非常相似 change/knapsack，但它不是硬币找零（这将要求最少的权重来获得准确的数量），而且它不是背包（重量没有值，就像我可以拥有超过 1 个背包）。
这个问题有通用的name/solution吗？
如果我错了请纠正我（不是最有效的），但我认为你可以把所有的重量都放在一个 max heap, and then use a greedy algorithm 中来选择集合。
你走在正确的轨道上。这个问题是通过一种改进的找零算法解决的：你不需要一个精确的解决方案，而是找到一个在不超过目标数量的情况下达到最高总数的解决方案。当然，如果您发现一个解决方案的不足小于任何剩余的集合元素，您将停止并报告该解决方案。
找到解决方案后，删除 "used" 权重并进行迭代，直到将它们全部分配完毕。迭代次数就是你需要的电梯数量。
如果按降序对元素进行排序，则会得到一个 "greedy" 从回溯开始的结果。我怀疑这在很多情况下都相当接近最优，特别是如果你记住结果，这样你就不会在下一次迭代中重复错误。
你可能会尝试一些病态的情况，例如限制为 100，以及像
这样的极端权重
[93, 91, ..., 5, 4, 4]
"greedy" 算法首先适用于 93+5，但随后适用于 91+4+4（更接近的解决方案）。这就是记忆化派上用场的地方。
这会让您找到解决方案吗？
这实际上是一个(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.
这里是人物在游乐设施的垃圾箱上绘制的物体图。就像装箱问题一样，我们希望尽量减少乘车次数 "used" 并且每个人占据一定的 "volume"（那个人的体重）。
如文章所述，装箱问题是 NP-hard。我们可以使用动态规划（但它仍然有 - 最坏情况 - 指数时间）。
Richard E. Korf 的论文 A New Algorithm for Optimal Bin Packing 讨论了一种精确解决此问题的算法。它的工作原理是首先使用启发式方法并计算下限，然后使用分支定界迭代地推导出比启发式更好的解决方案，直到达到下限，或者再也找不到解决方案。
input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]
output:
2
// [[250, 175, 120], [150]]
我的初步印象是，这看起来与动态规划硬币问题非常相似 change/knapsack，但它不是硬币找零（这将要求最少的权重来获得准确的数量），而且它不是背包（重量没有值，就像我可以拥有超过 1 个背包）。
这个问题有通用的name/solution吗？
如果我错了请纠正我（不是最有效的），但我认为你可以把所有的重量都放在一个 max heap, and then use a greedy algorithm 中来选择集合。
你走在正确的轨道上。这个问题是通过一种改进的找零算法解决的：你不需要一个精确的解决方案，而是找到一个在不超过目标数量的情况下达到最高总数的解决方案。当然，如果您发现一个解决方案的不足小于任何剩余的集合元素，您将停止并报告该解决方案。
找到解决方案后，删除 "used" 权重并进行迭代，直到将它们全部分配完毕。迭代次数就是你需要的电梯数量。
如果按降序对元素进行排序，则会得到一个 "greedy" 从回溯开始的结果。我怀疑这在很多情况下都相当接近最优，特别是如果你记住结果，这样你就不会在下一次迭代中重复错误。
你可能会尝试一些病态的情况，例如限制为 100，以及像
这样的极端权重[93, 91, ..., 5, 4, 4]
"greedy" 算法首先适用于 93+5，但随后适用于 91+4+4（更接近的解决方案）。这就是记忆化派上用场的地方。
这会让您找到解决方案吗？
这实际上是一个(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.
这里是人物在游乐设施的垃圾箱上绘制的物体图。就像装箱问题一样，我们希望尽量减少乘车次数 "used" 并且每个人占据一定的 "volume"（那个人的体重）。
如文章所述，装箱问题是 NP-hard。我们可以使用动态规划（但它仍然有 - 最坏情况 - 指数时间）。
Richard E. Korf 的论文 A New Algorithm for Optimal Bin Packing 讨论了一种精确解决此问题的算法。它的工作原理是首先使用启发式方法并计算下限，然后使用分支定界迭代地推导出比启发式更好的解决方案，直到达到下限，或者再也找不到解决方案。