arrays - 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 背包问题。可以用动态规划求解。经典背包问题与您的问题之间的区别在于，在您的情况下有多个背包。

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

来源——维基百科

Here's算法和很好的解释。