总和小于 N 的最少子集
Fewest subsets with sum less than N
我有一个特定的子问题，我无法找到最佳解决方案。这个问题类似于子集和组问题以及 space 填充问题，但我还没有在任何地方看到这个具体问题。我不一定需要最佳解决方案（因为我相对确定它是 NP-hard），但有效且快速的近似肯定就足够了。
问题：给定一个正值整数列表，找到包含整个整数列表的最少数量的不相交子集，其中每个子集的总和小于 N。显然没有整数原始列表可以大于N.
在我的应用程序中，我有很多列表，只要它们适合矩阵，我就可以将它们连接成矩阵的列。出于下游目的，我希望在生成的参差不齐的矩阵中有尽可能少的 "wasted" space，因此 space 填充相似性。
至此我采用了一种类似贪心的方法，从最大的整数开始向下处理，并在限制 N 下找到适合当前子集的最大整数。一旦最小的整数不再适合当前子集 I类似地继续下一个子集，直到所有数字都用完。这几乎肯定找不到最佳解决方案，但这是我能很快想到的最佳解决方案。
BONUS：我的应用程序实际上需要批次，其中每个批次中的子集数量有限制 (M)。因此，更大的问题是找到最少的批次，其中每个批次包含 M 个子集，并且每个子集的总和小于 N。
直接来自维基百科（有一些大胆的修正）：
In the bin packing problem, objects [Integers] of different volumes [values] must be
packed into a finite number of bins [sets] or containers each of volume V [summation of the subset < V] in
a way that minimizes the number of bins [sets] used. In computational
complexity theory, it is a combinatorial NP-hard problem.
https://en.wikipedia.org/wiki/Bin_packing_problem
据我所知，这正是您要找的。
我有一个特定的子问题，我无法找到最佳解决方案。这个问题类似于子集和组问题以及 space 填充问题，但我还没有在任何地方看到这个具体问题。我不一定需要最佳解决方案（因为我相对确定它是 NP-hard），但有效且快速的近似肯定就足够了。
问题：给定一个正值整数列表，找到包含整个整数列表的最少数量的不相交子集，其中每个子集的总和小于 N。显然没有整数原始列表可以大于N.
在我的应用程序中，我有很多列表，只要它们适合矩阵，我就可以将它们连接成矩阵的列。出于下游目的，我希望在生成的参差不齐的矩阵中有尽可能少的 "wasted" space，因此 space 填充相似性。
至此我采用了一种类似贪心的方法，从最大的整数开始向下处理，并在限制 N 下找到适合当前子集的最大整数。一旦最小的整数不再适合当前子集 I类似地继续下一个子集，直到所有数字都用完。这几乎肯定找不到最佳解决方案，但这是我能很快想到的最佳解决方案。
BONUS：我的应用程序实际上需要批次，其中每个批次中的子集数量有限制 (M)。因此，更大的问题是找到最少的批次，其中每个批次包含 M 个子集，并且每个子集的总和小于 N。
直接来自维基百科（有一些大胆的修正）：
In the bin packing problem, objects [Integers] of different volumes [values] must be packed into a finite number of bins [sets] or containers each of volume V [summation of the subset < V] in a way that minimizes the number of bins [sets] used. In computational complexity theory, it is a combinatorial NP-hard problem.
https://en.wikipedia.org/wiki/Bin_packing_problem
据我所知，这正是您要找的。