JavaScript实现近似等分装箱算法的技术问询

这是典型的带约束的多箱均衡装箱问题，属于NP-hard范畴，不存在能快速得到绝对最优解的多项式时间算法，但有成熟的启发式思路可以得到近似最优的分配结果，完全能满足你的需求。

核心实现思路 #

1. 预处理准备 #

• 先计算每个箱子当前的总重量与剩余容量（最大容量50减去当前总重）
• 将待分配的物品按从大到小排序：优先处理大物品能避免后期出现“大物品无处可放”的情况，同时更利于均衡各箱重量

2. 贪心分配策略（最易实现且效果稳定） #

推荐使用**“最轻箱优先”的变种贪心算法**：

• 对排序后的每个物品，筛选出所有剩余容量能容纳它的箱子
• 在这些箱子中，选择当前总重量最小的箱子放入该物品
• 这个逻辑的核心是优先给较轻的箱子补重，尽可能缩小各箱之间的重量差距

3. 进阶优化（针对小数据量） #

如果追求更均衡的结果，可以在基础贪心分配后加入微调逻辑：

• 计算所有箱子总重量的方差（方差越小，重量越均衡）
• 随机尝试交换两个箱子中的物品（需保证交换后两个箱子都不超过容量上限）
• 如果交换后方差降低，则保留该交换，重复迭代几次即可得到更优结果

JavaScript代码实现示例 #

// 待分配物品数组
const arr = [10, 5, 32, 10, 1, 25, 29];
// 箱子初始状态（用对象封装，自动计算总重量）
const bins = [
  { items: [23, 8, 1], get total() { return this.items.reduce((a, b) => a + b, 0); } },
  { items: [], get total() { return this.items.reduce((a, b) => a + b, 0); } },
  { items: [5, 11], get total() { return this.items.reduce((a, b) => a + b, 0); } },
  { items: [33], get total() { return this.items.reduce((a, b) => a + b, 0); } },
  { items: [], get total() { return this.items.reduce((a, b) => a + b, 0); } }
];
const MAX_CAPACITY = 50;

// 步骤1：待分配物品降序排序
const sortedItems = [...arr].sort((a, b) => b - a);

// 步骤2：贪心分配逻辑
for (const item of sortedItems) {
  // 筛选能容纳当前物品的箱子
  const eligibleBins = bins.filter(bin => bin.total + item <= MAX_CAPACITY);
  if (eligibleBins.length === 0) {
    throw new Error(`物品${item}无法放入任何箱子，请检查容量配置`);
  }
  // 选择当前总重量最小的箱子
  eligibleBins.sort((a, b) => a.total - b.total);
  const targetBin = eligibleBins[0];
  targetBin.items.push(item);
}

// 输出最终分配结果
bins.forEach((bin, index) => {
  console.log(`bin${index + 1} = [${bin.items.join(', ')}]     //${bin.total}`);
});

结果说明 #

运行上述代码后，会得到类似你预期的均衡分配结果。如果需要更极致的均衡，可以在分配完成后加入方差计算与微调逻辑，适合物品数量较少的场景；如果是大规模数据，建议使用遗传算法、模拟退火等启发式算法，但实现成本会更高。

内容的提问来源于stack exchange，提问作者Дмитрий Скрипко