寻求多属性物品均匀分箱的高效算法实现方案

核心逻辑 #

基于优先级分层+循环发牌+动态补位的思路，优先保证高优先级属性的均匀性，再在不破坏高优先级结果的前提下优化低优先级属性，完全避免暴力枚举，时间复杂度为O(n*k)（n为物品数，k为属性数），适配20-5000件物品的规模。

分步实现 #

1. 确定箱子基础容量 #

先明确每个箱子的目标负载：

• 基础容量 base = 总物品数 // 箱子数
• 余数 rem = 总物品数 % 箱子数
• 前rem个箱子的目标容量为base+1，剩余箱子为base
  这一步先保证总数量的均匀性，是所有属性分配的基础。

2. 最高优先级属性（颜色）分配 #

• 将所有物品按颜色分组（红/蓝/绿/黄）
• 对每个颜色组，采用循环发牌的方式分配：依次将当前颜色的物品分配给未达目标容量的箱子，循环往复直到该颜色组分配完毕
• 此步骤核心是保证每个颜色在箱子间的数量差尽可能小，因为优先级最高，必须优先满足

3. 次优先级属性（形状）优化 #

在颜色分配完成的基础上：

• 将所有物品按形状分组（圆形/方形/三角形）
• 对每个形状组，遍历箱子，优先将当前形状物品分配给该形状数量最少且未达目标容量的箱子
• 此步骤仅调整形状分布，不会改变已分配好的颜色数量，确保颜色的均匀性不受影响

4. 低优先级属性（尺寸/新旧）处理 #

按优先级依次处理尺寸、新旧属性，逻辑和形状优化完全一致：

• 按当前属性分组
• 对每组物品，优先分配给该属性数量最少的可用箱子
• 始终保证高优先级属性的分配结果不被修改

评分计算与验证 #

• 单属性评分：计算该属性每个取值在箱子间的最大数量差，将所有取值的差值相加，分数越低越好
• 总评分：按属性优先级顺序拼接各属性评分（不足两位补0），例如颜色评分3、形状评分2、尺寸评分1、新旧评分0，总评分为03-02-01-00
• 验证规则：高优先级评分权重远高于低优先级，因此00-99-99-99优于01-00-00-00

扩展性支持 #

后续新增重量、材质等属性时，只需：

1. 将新属性添加到优先级列表的末尾
2. 按照低优先级属性的处理逻辑，在已有分配结果上进行补位优化即可
   完全无需修改高优先级属性的分配逻辑，适配性极强

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