礼拜一-礼拜五:09.00 早上-06.00 下午

资讯中心

用不同长度轨道拼出目标距离怎样让段数最少:规则验证第06组

2026-11-14

轨道段允许重复使用时,先取最长的一段不一定能得到最少段数,甚至可能把剩余距离变成无法拼出的长度。逐个距离保存最佳拼法,可以明确区分可达与不可达。

本例采用的规则

本例每种轨道长度都是正整数且库存无限,目标必须精确达到,不能剪短。距离零用零段;对每个更大的距离,尝试移除一种不超过它的段长,从剩余距离的可达方案加一段,取段数最少的结果。相同段数取排序后段长序列字典序较小者。

独立输入与结果

可用段长[5, 7, 8, 11],每种无限,目标29。

距离 | 最少段数与一种排序拼法 0 | (0, ()) 1 | 不可达 2 | 不可达 3 | 不可达 4 | 不可达 5 | (1, (5,)) 6 | 不可达 7 | (1, (7,)) 8 | (1, (8,)) 9 | 不可达 10 | (2, (5, 5)) 11 | (1, (11,)) 12 | (2, (5, 7)) 13 | (2, (5, 8)) 14 | (2, (7, 7)) 15 | (2, (7, 8)) 16 | (2, (5, 11)) 17 | (3, (5, 5, 7)) 18 | (2, (7, 11)) 19 | (2, (8, 11)) 20 | (3, (5, 7, 8)) 21 | (3, (5, 5, 11)) 22 | (2, (11, 11)) 23 | (3, (5, 7, 11)) 24 | (3, (5, 8, 11)) 25 | (3, (7, 7, 11)) 26 | (3, (7, 8, 11)) 27 | (3, (5, 11, 11)) 28 | (4, (5, 5, 7, 11)) 29 | (3, (7, 11, 11)) 最长优先取段[11, 11, 7],剩余0。

表中的编号仅用于区分当前案例里的对象,不能与数值大小或另一份记录中的身份混淆。先核对输入、单位和边界约定,再跟随过程检查输出。空列表、不存在和数值零各有不同含义,分数则保留精确形式便于复算。

检查与练习

输出各段长度相加必须等于目标,段数等于序列长度。不可达状态不能初始化为零段,否则后面的计算会凭空获得免费距离。对照的最长优先策略只会不断取当前不超过余量的最大段,不回退。

先找一个最长优先失败但完整搜索成功的案例,理解为什么局部选择不能保证全局结果。即使这次贪心碰巧最优,也只说明当前输入恰好如此。动态规划表保存所有中间距离,便于检查错误从哪个余量开始传播。

结论适用范围

这里不考虑接缝形状、不同段的重量、价格或库存限制。若每种长度数量有限,状态就需要包含剩余库存或采用不同算法;不能把无限库存的结论直接搬到限量材料的关卡。

这是一份可重复演算的游戏知识记录,结论只对写明的输入与规则成立。练习时可以先改变一个条件,再对照中间记录寻找变化从哪一步开始。若结果不同,应先确认操作顺序和边界定义,而不是只改最后一个数字;原始输入与完整过程应一起保留。