如何将非负数值数组划分为M个子集，最小化最大子集和？

这是一个经典的NP-hard优化问题，和Kadane算法（用于求解最大连续子数组和）没有直接关联。根据元素类型（整数/浮点数）和数据规模，我们可以选择不同的解法：

核心思路说明 #

问题的目标是将数组划分为M个子集，让所有子集的最大和尽可能小。这个问题的下界是数组中的最大值（至少有一个子集要包含这个元素），上界是数组总和（当M=1时的情况）。

一、贪心近似算法（高效，适用于整数/浮点数） #

最优贪心策略 #

每次将当前未分配的最大元素加入当前和最小的子集。这个策略的近似比为2（即结果不会超过最优解的2倍），在大多数场景下能得到接近最优的结果，且实现简单高效。

Python实现 #

def partition_min_max_sum(arr, M):
    # 降序排序，优先处理大元素，避免大元素被孤立或导致局部最优
    sorted_arr = sorted(arr, reverse=True)
    # 初始化M个子集及其和
    subsets = [[] for _ in range(M)]
    subset_sums = [0.0] * M

    for num in sorted_arr:
        # 找到当前和最小的子集索引
        min_idx = subset_sums.index(min(subset_sums))
        subsets[min_idx].append(num)
        subset_sums[min_idx] += num

    return subsets, max(subset_sums)

# 测试示例1
arr1 = [1, 4, 5, 3]
M1 = 2
subsets1, max_sum1 = partition_min_max_sum(arr1, M1)
print(f"示例1结果：子集{subsets1}，最小化后的最大和为{max_sum1}")

# 测试示例2
arr2 = [3, 10, 7, 2]
M2 = 3
subsets2, max_sum2 = partition_min_max_sum(arr2, M2)
print(f"示例2结果：子集{subsets2}，最小化后的最大和为{max_sum2}")

你的贪心策略的局限性 #

你构思的“升序排序后交替分配最小/最大元素”的方法，在很多场景下会得到次优解。比如数组[1,2,3,4,5,6,7,8,9,10]，M=3时，你的方法会得到最大和为22的结果，而最优解的最大和仅为19，差距明显。

二、精确解法（仅适用于整数元素，小数据规模） #

对于整数元素且数据量不大的情况，可以用二分查找+可行性检查来得到精确解：

1. 二分查找范围：low = max(arr)，high = sum(arr)
2. 对每个中间值mid，检查是否能将数组划分为M个子集，每个子集和不超过mid

伪代码 #

function can_split(arr, M, target_sum):
    # 降序排序后尝试分配，提高检查效率
    sorted_arr = sorted(arr, reverse=True)
    subset_sums = [0] * M
    for num in sorted_arr:
        placed = False
        for i in 0 to M-1:
            if subset_sums[i] + num <= target_sum:
                subset_sums[i] += num
                placed = True
                break
        if not placed:
            return False
    return True

function find_exact_min_max(arr, M):
    low = max(arr)
    high = sum(arr)
    best = high
    while low <= high:
        mid = (low + high) // 2
        if can_split(arr, M, mid):
            best = mid
            high = mid - 1
        else:
            low = mid + 1
    return best

注意：这里的can_split用的是贪心检查，对于某些特殊数组可能无法正确判断（属于近似检查），若要完全精确，需要用动态规划，但动态规划的时间复杂度为O(N*M*S)（S为数组总和），仅适用于小数据。

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