用户分组值均衡分配的JavaScript算法实现问题

需求描述 #

给定一组包含value属性的用户数据，需将其划分为指定数量的分组，必须满足两个核心要求：

• 各组的value总和尽可能接近
• 各组的用户数量差值不超过1

示例输入与预期输出 #

const users = [
  {name: 'a',value: 1}, {name: 'b',value: 2}, {name: 'c',value: 3},
  {name: 'd',value: 4}, {name: 'e',value: 5}, {name: 'f',value: 6},
  {name: 'g',value: 7}, {name: 'h',value: 8}, {name: 'i',value: 9}
];
const numGroups = 3;
// 预期输出
const result = [
  {users: [{name: 'a',value: 1}, {name: 'e',value: 5}, {name: 'i',value: 9}], valueTot: 15},
  {users: [{name: 'b',value: 2}, {name: 'f',value: 6}, {name: 'g',value: 7}], valueTot: 15},
  {users: [{name: 'c',value: 3}, {name: 'd',value: 4}, {name: 'h',value: 8}], valueTot: 15}
];

现有算法问题 #

以下两种JavaScript算法均无法满足需求：

算法1：简单轮询分配 #

function divideUsersIntoGroups(users, numGroups) {
  users.sort((a, b) => a.value - b.value);
  const groupedUsers = Array.from({ length: numGroups }, () => []);
  users.forEach((user, index) => {
    const groupIndex = index % numGroups;
    groupedUsers[groupIndex].push(user);
  });
  return groupedUsers;
}

算法2：基于目标差值分配 #

function divideUsersIntoGroups(users, numGroups) {
  const totalSum = users.reduce((acc, user) => acc + user.value, 0);
  const targetSum = totalSum / numGroups;
  users.sort((a, b) => a.value - b.value);
  const groupedUsers = Array.from({ length: numGroups }, () => ({ users: [], valueTot: 0 }));
  users.forEach(user => {
    let minDiff = Infinity;
    let bestGroupIndex = 0;
    groupedUsers.forEach((group, index) => {
      const currentDiff = Math.abs(group.valueTot + user.value - targetSum);
      if (currentDiff < minDiff) {
        minDiff = currentDiff;
        bestGroupIndex = index;
      }
    });
    groupedUsers[bestGroupIndex].users.push(user);
    groupedUsers[bestGroupIndex].valueTot += user.value;
  });
  return groupedUsers;
}

额外测试用例 #

测试用例1 #

const users = [
  { name: 'a', value: 1 },{ name: 'b', value: 2 },{ name: 'c', value: 3 },
  { name: 'd', value: 24 },{ name: 'e', value: 30 },{ name: 'f', value: 50 }
];
// 预期输出
const result = [
  {users: [{name: 'f',value: 50}, {name: 'a',value: 1}], valueTot: 51},
  {users: [{name: 'e',value: 30}, {name: 'b',value: 2}], valueTot: 32},
  {users: [{name: 'd',value: 24}, {name: 'c',value: 3}], valueTot: 27}
];

测试用例2 #

const users = [
  { name: 'a', value: -5 },{ name: 'b', value: -2 },{ name: 'c', value: 0 },
  { name: 'd', value: 0 },{ name: 'e', value: 3 },{ name: 'f', value: 5 },
  { name: 'g', value: 8 },{ name: 'h', value: 9 },{ name: 'i', value: 9 },
  { name: 'j', value: 10 },{ name: 'k', value: 34 }
];
// 预期输出
const result = [
  {users: [{name: 'k',value: 34},{name: 'a',value: -5},{name: 'b',value: -2},{name: 'c',value: 0}], valueTot: 27},
  {users: [{name: 'j',value: 10},{name: 'i',value: 9},{name: 'e',value: 3},{name: 'd',value: 0}], valueTot: 22},
  {users: [{name: 'h',value: 9},{name: 'g',value: 8},{name: 'f',value: 5}], valueTot: 22}
];

优化后的算法 #

function divideUsersIntoGroups(users, numGroups) {
  // 计算每组的最大用户容量，确保数量差不超过1
  const totalUsers = users.length;
  const minUsersPerGroup = Math.floor(totalUsers / numGroups);
  const groupsWithExtra = totalUsers % numGroups;
  
  // 按value降序排序，优先分配大数值用户，避免集中扎堆
  const sortedUsers = [...users].sort((a, b) => b.value - a.value);
  
  // 初始化分组，包含容量限制
  const groups = Array.from({ length: numGroups }, (_, idx) => ({
    users: [],
    valueTot: 0,
    maxCapacity: idx < groupsWithExtra ? minUsersPerGroup + 1 : minUsersPerGroup
  }));
  
  // 全局目标总和
  const globalTarget = users.reduce((acc, u) => acc + u.value, 0) / numGroups;
  
  // 逐个分配用户
  for (const user of sortedUsers) {
    let bestGroup = null;
    let minDiff = Infinity;
    
    for (const group of groups) {
      // 跳过已达容量上限的组
      if (group.users.length >= group.maxCapacity) continue;
      
      const newSum = group.valueTot + user.value;
      const diff = Math.abs(newSum - globalTarget);
      
      // 优先选择差值最小的组，差值相同时选当前总和更小的组
      if (diff < minDiff || (diff === minDiff && group.valueTot < (bestGroup?.valueTot ?? Infinity))) {
        minDiff = diff;
        bestGroup = group;
      }
    }
    
    if (bestGroup) {
      bestGroup.users.push(user);
      bestGroup.valueTot += user.value;
    }
  }
  
  // 转换为预期输出格式
  return groups.map(({ users, valueTot }) => ({ users, valueTot }));
}

算法核心逻辑 #

1. 容量预控制：提前计算每组的最大用户数，严格保证各组数量差不超过1
2. 降序优先分配：先处理大数值用户，从根源避免大值集中导致的总和失衡
3. 多维度选组：分配时优先选择还有容量、且添加后总和最接近目标值的组；差值相同时选当前总和更小的组，进一步平衡
4. 兼容负数场景：基于全局平均值计算差值，绝对值处理确保负数value也能正确分配

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