车辆移动问题——2004年第2期题解

问题描述见《程序员》杂志2004年第2期。算法分析建立数学模型我们先来分析一下这道题。如果令 x_i 为车道 i 的初始车辆数,则(x_1,x_2,x_3,...,x_n)为所给的初始车辆序列。如果令=/n 为每车道最后要达到的平均值,则最后要达到的目标序列为(,,,...,)。本题是求从初始序列到最后的目标序列的一个最少移动(i,m)集合。在这里我们先要抓住一个隐含的相对不变量,这个相对不变量就是每个车道在完成任务的过程中向外移动的总车辆数,