如何基于重量、体积双约束以最优方式拆分bag对象列表

单约束拆分效果异常修复 #

你当前体积拆分效果不达标的核心原因是优先队列排序规则未匹配维度要求：

• 重量单约束拆分：原有逻辑正确，优先队列按weightPerQty升序排列即可得到最优解
• 体积单约束拆分：需要把优先队列的排序规则改为按volumePerQty升序排列，修改后即可达到和重量拆分一致的最优效果

双约束（重量+体积同时限制）最优拆分算法 #

你遇到的场景属于可拆分二维多箱装箱问题，因为允许拆分bag的数量，无需处理NP复杂逻辑，用以下贪心算法即可得到最少打包袋的最优拆分结果：

算法步骤 #

• 每个打包袋初始化时记录两个剩余容量：剩余承重remW = 用户输入最大重量、剩余容积remV = 用户输入最大体积
• 优先队列动态排序规则：计算每个bag可装入当前打包袋的最大数量maxPossibleQty = min(remW / bag.weightPerQty, remV / bag.volumePerQty)，按maxPossibleQty降序排列，优先取可装数量最多的bag

1. 将所有初始bag对象存入优先队列，新建第一个打包袋
2. 从优先队列取出排序第一的bag，计算实际可装入数量qty = min(bag.quantity, maxPossibleQty)
3. 将qty数量的bag装入当前打包袋，更新当前打包袋的剩余容量：

   remW = remW - qty * bag.weightPerQty;
   remV = remV - qty * bag.volumePerQty;
   

4. 如果原bag的quantity > qty，将剩余数量的bag重新放回优先队列
5. 如果当前打包袋的remW == 0 或 remV == 0（任意一个资源耗尽即为装满），新建打包袋并重置remW、remV为初始最大值
6. 重复步骤2-5，直到优先队列为空

边界说明 #

如果你的「最优」定义不是最少打包袋数量，而是尽可能减少bag拆分次数，只需要调整优先队列的排序规则，将maxPossibleQty和bag的总数量做加权计算即可。

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