正整数列表的最小拆分问题：子列表总和不超过阈值N

问题描述 #

给定由正整数组成的列表[x₁, x₂, ..., xₙ]，需将其拆分为最少数量的子列表，每个子列表的元素总和不超过给定值N。

示例：当列表为[67, 56, 12345, 555555, 555555, 555555]、N=1000000时，最优拆分方案为[[555555, 12345, 67, 56], [555555], [555555]]，仅需3个子列表。

本人提出的试探解法 #

1. 对列表进行降序排序；
2. 取出当前列表中的最大值，逐个加入最小值，确保加入后子列表总和不超过N；
3. 移除已使用的元素，重复步骤2直至列表为空。

核心结论 #

这个问题本质是装箱问题（Bin Packing Problem），属于NP-hard问题——不存在多项式时间的精确解法（除非P=NP）。你提出的贪心策略是一种近似算法，在大多数实际场景中能得到接近最优的结果，但无法保证所有情况都能得到最少拆分次数。

关于近似算法的补充说明 #

• 你的策略核心是“最大元素优先，用最小元素填充剩余空间”，属于贪心算法的一种，最坏情况下拆分次数不会超过最优解的2倍；
• 若想获得更优的近似结果，可以使用**首次适配递减（First Fit Decreasing, FFD）**算法：先将列表降序排序，然后依次将每个元素放入第一个能容纳它的已存在子列表中，若没有则新建子列表。该算法的性能比更优，最坏情况下拆分次数不超过⌈11/9 * OPT⌉（OPT为最优拆分次数）；
• 如果要求绝对最优解，只能通过暴力枚举或分支定界等指数时间复杂度的算法实现，但仅适用于元素数量较少的场景。

内容的提问来源于stack exchange，提问作者Stat_prob_001