围成一圈的机关若不允许相邻位置同时启用,首尾两格也构成冲突。直接把它当作一条直线,会漏掉这一对相邻关系,可能算出实际上无法同时开启的组合。
明确本例规则
本例每格能量为非负整数,允许一个也不选。分别考虑不选末格、以及不选首格的两条线性子问题,每条用动态规划比较跳过当前格与选择它并跳过前一格。最后比较两个子问题总分,同分保留第一种情况。
输入与逐步结果
十一格围成一圈,编号零至十,能量为[3, 3, 15, 7, 19, 18, 0, 13, 5, 1, 8]。
不选末格的逐步最优(总量、编号): (0, []) (3, [0]) (3, [0]) (18, [0, 2]) (18, [0, 2]) (37, [0, 2, 4]) (37, [0, 2, 4]) (37, [0, 2, 4]) (50, [0, 2, 4, 7]) (50, [0, 2, 4, 7]) (51, [0, 2, 4, 7, 9]) 不选首格的逐步最优: (0, []) (3, [1]) (15, [2]) (15, [2]) (34, [2, 4]) (34, [2, 4]) (34, [2, 4]) (47, [2, 4, 7]) (47, [2, 4, 7]) (48, [2, 4, 7, 9]) (55, [2, 4, 7, 10]) 最终选择[2, 4, 7, 10],总能量55。
编号仅标识本次案例中的对象,不能把它当成重要性排名。复算时先保留原输入,再按表格顺序记录中间状态。零值、空列表和未到达各有含义,不能因为显示相似就合并处理。需要分数的地方保存精确值,小数只用于阅读。
结果如何核对
空选择的总能量为零。每个线性子问题同分优先跳过当前格,使还原路径稳定。选中编号排序后,任意两格的环上距离都不能为一;首格和末格也必须核对,不能只检查列表中连续的编号。
可用所有位置子集做小规模复核,逐个剔除相邻冲突后比较总能量。输出不一定唯一,验证时应同时检查合法性和总分;只因另一份答案编号不同就判错,会把同样最优的组合误删。
使用边界
这里冲突只发生在直接相邻格之间,没有间隔两格的干扰、固定数量要求或额外联动。若规则要求至少选一个且允许负值,空方案的处理就必须改变,本例的零初值不能原样照用。
练习可以先保持其他条件不变,只调整一项输入,观察哪个中间步骤首先产生差异。如果结果不同,先确认单位、端点和同值处理是否一致,再查具体运算。最终答案应与输入和过程一起保存,才方便判断这份结论适用于什么情境。
