高效实现行李箱重量凑8倍数的组合与填充算法

需求说明 #

你需要对给定的行李箱列表做分组，满足规则：

• 每个suitcase对象包含name（名称）、weight（重量）两个属性
• 每组总重量必须是8的倍数
• 最终返回分组后的元组列表
• 仅当行李箱无法通过互相组合凑出8的倍数总重时，才允许用重量为1的单位填充补足，该操作是最后兜底手段
  参考示例代码：

sc1 = suitcase("sc1", 5)
sc2 = suitcase("sc2", 1)
sc3 = suitcase("sc3", 3)
sc4 = suitcase("sc4", 14)
sc5 = suitcase("sc5", 4)
sc6 = suitcase("sc6", 1)
sc7 = suitcase("sc7", 8)
sclist = [sc1,sc2,sc3,sc4,sc5,sc6,sc7]

sorted_tuple = sort_suitcases(sclist)
# 以下为合法输出之一，符合规则的结果不唯一
sorted_tuple = [(sc7),(sc1,sc3),(sc4,sc2,sc6),(sc5,{1,1,1,1})]
# 所有行李箱凑成单个大组只要总重为8的倍数，同样符合要求

你当前用的双层遍历暴力查组合的方案时间复杂度是O(n²)，数据量大的时候性能很差，可以用按模8余数分桶的思路把复杂度降到O(n)。

具体实现逻辑 #

核心思路是不用枚举所有重量组合，只需要按重量对8取模的余数分类配对：

1. 预处理分桶：初始化8个列表（桶），编号0到7，遍历所有行李箱，把每个箱子放到weight % 8对应编号的桶里。比如重量8的sc7模8余0，进0号桶；重量14的sc4模8余6，进6号桶。
2. 优先配对互补余数：这一步不需要填充，先把能直接凑成8倍数的组合挑出来：
   • 0号桶里的每个箱子单独成组，自身重量已经是8的倍数，直接加入结果列表
   • 1号桶（余1）和7号桶（余7）配对：每次从两个桶各取1个箱子凑成一组，总余1+7=8≡0 mod8，直到其中一个桶被取空
   • 2号桶（余2）和6号桶（余6）配对：逻辑同上，1个余2+1个余6凑一组，直到某一桶空
   • 3号桶（余3）和5号桶（余5）配对：逻辑同上，1个余3+1个余5凑一组，直到某一桶空
   • 4号桶（余4）两两配对：每次取2个余4的箱子凑一组，总余4+4=8≡0 mod8，最后桶里剩下0或1个箱子
3. 处理剩余未配对的箱子：
   经过上一步后，剩下的箱子只会分布在1、2、3号桶，以及最多1个在4号桶。这时候优先在剩余箱子里找余数和为8的组合凑组，比如2个余3加1个余2总余8、4个余1总余4搭配剩下的1个余4总余8、2个余2总余4搭配剩下的1个余4总余8等，尽量把剩余箱子凑成符合要求的组，减少后续填充量。
4. 兜底填充：最后剩下的没法互相凑的箱子，计算当前组总重量模8的差值，差多少就补多少个重量为1的填充单位，凑到总重为8的倍数即可。

这个方案全程只需要线性遍历，不需要双层循环查组合，哪怕是十万级以上的行李箱数据也能快速处理。如果要求填充单位用得最少，只需要在剩余箱子凑组环节优先选余数和刚好为8的组合，把需要补的差值压到最低即可。

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