正整数数组最小子集划分算法：子集和不超过给定值k

嘿，这个问题本质就是经典的装箱问题（Bin Packing Problem）——我们要把所有数组元素放进"容量为k的箱子"（也就是子集）里，用最少的箱子数。你提到的降序贪心思路是这个问题里最实用的近似解法之一，实际场景下效果非常好，下面给你拆解清楚：

核心实现步骤 #

1. 先给数组降序排序 #

这一步是关键！先把大元素安排好，能避免后期大元素找不到合适的子集被迫新开箱子的情况。比如如果先塞一堆小元素占满了箱子，最后剩个大元素，明明之前有箱子能塞下，但空间已经被小元素占了，就得多开一个没必要的箱子。

2. 逐个分配元素到子集 #

初始化一个空列表用来记录每个子集的当前元素和，然后遍历排序后的每个元素：

• 挨个检查已有的子集，如果某个子集加上当前元素后和不超过k，就把元素放进去，更新这个子集的和
• 如果所有现有子集都放不下这个元素，就新建一个子集，把元素放进去

举个实际例子：
假设数组是[5,4,3,2,2]，k=6
排序后变成[5,4,3,2,2]

• 第一个元素5：没子集，新建子集[5]（和为5）
• 第二个元素4：现有子集剩余容量1，放不下，新建子集[4]（和为4）
• 第三个元素3：前两个子集剩余容量分别是1和2，都放不下，新建子集[3]（和为3）
• 第四个元素2：第二个子集剩余容量2刚好能放下，把它加进去，子集变成[4,2]（和为6）
• 第五个元素2：第三个子集剩余容量3能放下，加进去后子集变成[3,2]（和为5）
  最终得到3个子集，这就是最优解。

补充说明 #

注意：这个降序贪心算法是近似算法，理论上最坏情况下结果是最优解的1.5倍，但绝大多数实际场景里，它的结果要么等于最优解，要么非常接近。如果必须要绝对最优解，就得用动态规划或回溯法，但时间复杂度会飙升到O(n*2^n)，只适合小体量的数组。

简单实现的伪代码 #

def min_subset_count(arr, k):
    # 先对数组降序排序
    arr.sort(reverse=True)
    subset_sums = []  # 存储每个子集的当前元素和
    
    for num in arr:
        placed = False
        # 遍历现有子集，尝试放入
        for i in range(len(subset_sums)):
            if subset_sums[i] + num <= k:
                subset_sums[i] += num
                placed = True
                break
        # 所有子集都放不下，新建一个
        if not placed:
            subset_sums.append(num)
    
    return len(subset_sums)

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