n 个物体所需的最小盒子数

Question

有 n 个物体具有不同的重量。我们必须找到包装所有重量所需的最小盒子数量，其中每个盒子的最大重量为 K。盒子可以容纳任意数量的物体，但重量应小于或等于给定的重量 K。

所有权重均小于或等于 K。

例如，令 K= 13 且对象为 {2,3,4,5,6,7,8,9}，则所需的最小框数为 4，即 {4,9}、{5,8}， {6,7}, {2,3}

我应该如何解决这个问题？

Answer 1

这几乎类似于0-1背包问题。可以使用动态规划来解决。经典背包问题与您的问题之间的区别在于，在您的情况下有多个背包。

背包问题或背囊问题是组合优化中的问题：给定一组物品，每个物品都有一个重量和一个值，确定要包含在集合中的每个物品的数量，以使总重量小于或等于给定的限制和总值尽可能大。

来源 - 维基百科

这是算法和一个很好的解释。