保持项顺序的可变大小物品N组均衡分配算法实现问询

需求核心 #

将有序的项列表划分为N个总大小尽可能相近的分组，同时保留项的原有顺序。根据你的示例，实际需求应为将原列表分割为N个连续子序列（组内项是原列表的连续片段），而非将单个项随意分配到不同组。

原代码问题分析 #

你提供的代码实现的是「非连续项贪心分配」——每次将当前项放到当前总大小最小的组。这种方式能平衡组大小，但会打破项的连续分组，输出结果和你的期望不符：

Group 1 (total size 5): Item A
Group 2 (total size 6): Item B, Item D, Item E
Group 3 (total size 8): Item C

解决方案思路 #

1. 贪心连续分段（近似解，简单高效） #

基于目标均值的贪心策略，尽可能让每组大小接近总均值，同时保证剩余项能分成剩下的组：

• 计算总大小的均值target = 总大小 / N
• 遍历项累加当前组大小，若加入下一项会超过均值且剩余项足够分剩下的组，则结束当前组，开始新组

代码实现

function splitIntoContinuousGroups(items, numGroups) {
    const totalSize = items.reduce((sum, item) => sum + item.size, 0);
    const target = totalSize / numGroups;
    const groups = [];
    let currentGroup = [];
    let currentSize = 0;
    let remainingGroups = numGroups;

    for (let i = 0; i < items.length; i++) {
        const item = items[i];
        const remainingItems = items.length - i - 1;
        // 检查剩余项是否能分成剩下的组（每组至少1个项）
        const canSplitRemaining = remainingItems >= remainingGroups - 1;

        if (currentSize + item.size <= target || !canSplitRemaining) {
            currentGroup.push(item);
            currentSize += item.size;
        } else {
            groups.push({ items: currentGroup, totalSize: currentSize });
            currentGroup = [item];
            currentSize = item.size;
            remainingGroups--;
        }
    }

    // 加入最后一组
    groups.push({ items: currentGroup, totalSize: currentSize });

    // 输出结果
    groups.forEach((group, index) => {
        console.log(`Group ${index + 1} (total size ${group.totalSize}): ${group.items.map(item => item.title).join(', ')}`);
    });

    return groups;
}

// 测试示例
const items = [
    { title: 'Item A', size: 5 },
    { title: 'Item B', size: 1 },
    { title: 'Item C', size: 8 },
    { title: 'Item D', size: 2 },
    { title: 'Item E', size: 3 },
];

splitIntoContinuousGroups(items, 3);

输出结果

Group 1 (total size 6): Item A, Item B
Group 2 (total size 8): Item C
Group 3 (total size 5): Item D, Item E

2. 动态规划最优解（精确平衡） #

如果需要找到绝对最优的连续分段（各组大小的平方和最小，即最接近均值），可以用动态规划：

• 预处理前缀和数组，快速计算任意区间的总大小
• 定义dp[k][i]为前i个项分成k组的最小平方和
• 状态转移：dp[k][i] = min(dp[k-1][j] + (前缀和[i]-前缀和[j])²)，遍历所有可能的分割点j

代码实现

function splitIntoOptimalContinuousGroups(items, numGroups) {
    const n = items.length;
    // 计算前缀和数组
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + items[i].size;
    }

    // DP表：dp[k][i] = 将前i个项分成k组的最小平方和
    const dp = Array.from({ length: numGroups + 1 }, () => new Array(n + 1).fill(Infinity));
    // 初始化：分成1组的情况
    for (let i = 1; i <= n; i++) {
        dp[1][i] = prefixSum[i] ** 2;
    }

    // 填充DP表
    for (let k = 2; k <= numGroups; k++) {
        for (let i = k; i <= n; i++) { // 分成k组至少需要k个项
            for (let j = k - 1; j < i; j++) { // 前k-1组至少k-1个项
                const currentCost = dp[k-1][j] + (prefixSum[i] - prefixSum[j]) ** 2;
                if (currentCost < dp[k][i]) {
                    dp[k][i] = currentCost;
                }
            }
        }
    }

    // 回溯找分割点
    const groups = [];
    let currentIndex = n;
    for (let k = numGroups; k >= 1; k--) {
        for (let j = k - 1; j < currentIndex; j++) {
            if (dp[k][currentIndex] === dp[k-1][j] + (prefixSum[currentIndex] - prefixSum[j]) ** 2) {
                groups.unshift(items.slice(j, currentIndex));
                currentIndex = j;
                break;
            }
        }
    }

    // 输出结果
    groups.forEach((group, index) => {
        const totalSize = group.reduce((sum, item) => sum + item.size, 0);
        console.log(`Group ${index + 1} (total size ${totalSize}): ${group.map(item => item.title).join(', ')}`);
    });

    return groups;
}

// 测试示例
splitIntoOptimalContinuousGroups(items, 3);

方案选择 #

• 若追求简单高效且结果足够满足需求，优先选择贪心连续分段
• 若需要绝对最优的分组平衡，选择动态规划实现
• 若允许组内项非连续但保持顺序，你的原代码是可行的，可通过优先队列优化查找最小组的效率

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