如何用有限数量垫片无间隙填充间隙？解决贪心算法剩余问题

需求说明 #

• 使用有限数量的垫片完全填充指定尺寸间隙，要求无剩余空间且使用的垫片数量最少

给定参数 #

垫片规格数组 #

const SPACERS = [
  .05,
  .0505,
  .051,
  .052,
  .054,
  .058,
  .06,
  .07,
  .08,
  .09,
  .1,
  .2,
  .4,
  .8,
  1.6,
  3.2
]

各规格垫片数量限制 #

const SPACERQTY = {
  "0.05": 52,
  "0.0505" : 8,
  "0.051" : 40,
  "0.052" : 40,
  "0.054" : 40,
  "0.058" : 40,
  "0.06" : 36,
  "0.07" : 36,
  "0.08" : 36,
  "0.09" : 36,
  "0.1" : 48,
  "0.2" : 16,
  "0.4" : 16,
  "0.8" : 16,
  "1.6" : 8,
  "3.2" : 8,
}

当前问题 #

现有getSpacersBetweenKnives函数采用从大到小选取垫片的贪心算法，处理stripWidth=20.998时，剩余0.008间隙无法填充，输出组合为：

[3.2,3.2,3.2,3.2,3.2,3.2,1.6,0.1,0.09]

而存在能完全填充的组合（注：原组合中.009应为笔误，修正为.09）：

[3.2,3.2,3.2,3.2,3.2,3.2,.8,.09,.058,.05]

解决方案：用回溯+剪枝替代贪心算法 #

贪心算法的本质是局部最优，无法保证全局最优（完全填充），因此需要改用带剪枝的回溯搜索：

核心逻辑 #

1. 预处理垫片：将垫片按尺寸从大到小排序，优先尝试大垫片，减少无效搜索分支
2. 回溯搜索流程
   • 每一步尝试当前最大可用垫片（满足：尺寸≤剩余间隙、库存数量>0）
   • 若当前路径无法填充剩余间隙，回溯：移除刚选的垫片，尝试下一个更小规格的垫片
   • 记录所有能完全填充的组合，最终筛选出数量最少的那个
3. 关键剪枝优化
   • 若当前已选垫片数量≥已找到的最优解数量，直接终止该分支（不可能更优）
   • 若剩余间隙小于当前最小垫片尺寸，直接终止该分支
   • 跳过重复规格的垫片，避免重复搜索相同组合

注意事项 #

• 浮点数精度处理：小数计算易产生精度误差，建议将所有数值乘以10000转为整数运算，或设置误差阈值（如1e-6），当剩余间隙≤该阈值时视为填充完成
• 状态跟踪：搜索过程中需实时跟踪剩余间隙、各垫片的剩余库存、当前已选垫片列表
• 最优解缓存：一旦找到完全填充的组合，后续搜索只要当前数量超过该组合长度，直接剪枝

针对当前案例的调整说明 #

在贪心算法选择1.6垫片的步骤，剩余间隙为20.998 - 6*3.2 = 1.798：

• 贪心选1.6后剩余0.198，后续选0.1+0.09后剩余0.008无法填充
• 回溯算法会尝试跳过1.6垫片，选择下一个大尺寸的0.8，剩余间隙变为1.798 - 0.8 = 0.998，接着继续搜索小垫片组合，最终找到能完全填充的0.09+0.058+0.05组合，实现无剩余填充

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