中山纪念中学信息学奥林匹克算法设计题选
定一种最优化的决策。这种问题用枚举法把所有决策都找出来再进行判断当然也可以做到，但往往在时间与内存空间上出问题。这种情况都用动态规划法来解，以求得最优策略。 最优策略可解释为：无论过程的初始状态或初始决策怎样，以后的最优策略只取决于由最初策略所确定的当前状态。例如：从城市A1出发经过A2，A3，A4到达A5，如果这条路线是从A1到A5的最短路线，则由A2经A3，A4到达A5也一定是从A2到A5的最短路线。根据最优原理的原则，动态规划在每种状态下列出各种可能的局部解，然后按某些条件，从局部解中挑出那些有可能产生最佳解的结果而舍弃其余，从而大大缩小了计算量。 例：如上图：顶点（1）为起点，顶点（12）为终点，试找出从起点至终点的一条最短路径。 分析：由上图可知，要找（1）到（12）的最短路线，必须分四步走，D1到D2有四个选择，D2到D3有三个
选择，D3到D4有三个选择，D4到D5只有一个选择。要找到的（1）到（12）的最短路径，也同样应该是该条路线中某个点到（12）的最短路径。因此，我们可以反其道而行之，从（12）出发，找出到每一个点的最短路线。例如：
（1）（12）到（11）的最短路线为5，（12）—（10）：2，（12）—（9）：4 （2）（12）—（8）：7；（12）—（7）：5；（12）—（6）：6
（3）（12）—（5）：15；（120—（4）：18；（12）—（3）：8；（12）—（2）：7 （4）（12）—（1）：15
并且可知：路线为：（1）—（3）—（6）—（10）—（12） 程序如下，请看懂后自己再编一次：
const d:array[1..12,1..12] of integer=(
(0,9,7,3,2,0,0,0,0,0,0,0), (9,0,0,0,0,4,2,11,0,0,0,0), (7,0,0,0,0,2,7,0,0,0,0,0), (3,0,0,0,0,0,0,11,0,0,0,0), (2,0,0,0,0,0,11,8,0,0,0,0), (0,4,2,0,0,0,0,0,6,4,0,0), (0,2,7,0,11,0,0,0,4,3,0,0), (0,11,0,11,8,0,0,0,0,5,6,0), (0,0,0,0,0,6,4,0,0,0,0,4), (0,0,0,0,0,4,3,5,0,0,0,2), (0,0,0,0,0,0,0,6,0,0,0,5), (0,0,0,0,0,0,0,0,4,2,5,0)); var lenmin:array[1..12] of integer; father:array[1..12] of integer; x,y,z,min:integer; begin
lenmin[12]:=0; father[12]:=0;
for x:=11 downto 1 do begin min:=10000;
for y:=x to 12 do begin if d[x,y]<>0 then begin
if lenmin[y]+d[x,y] 第 21 页 共 31页 中山纪念中学信息学奥林匹克算法设计题选 end; end; lenmin[x]:=min; father[x]:=z; end; x:=1; writeln(lenmin[1]); repeat write(x,'-->'); x:=father[x]; until x=0; end. 2、动态规划：设有由N个不相同的整数组成的数列，记为A1，A2，??AN，且AI<>AJ（I<>J）。请找出此数列中最长递增子序列。N及N个数由键盘输入。 分析：该题中动态规划与分治结合起来的作用是： （1）找出由数组中第一个数出发的最长递增子序列，并记下起始点及长度为暂时结果； （2）从上述子序列后第一个数再开始找其最长递增子序列，如果长度大于（1）中的长度则把此子序列的起始点及长度记下暂时结果。 （3）继续（2），直到数组中的数用完，把记下的结果从数组中找出子序列打印出来即可。 3、动态规划：下图是城市道路的示意图。每条边上的数字为该段街道的长度。求从A地到B地（只允许往右或往上走）的最短路径及长度。 4、动态规划：某工厂购进1000台机器，准备生产P1和P2两种产品。若生产产品P1，每台机器每年可收入4500元，但机器损坏率达65%。若生产产品P2，每台机器每年可收入3500元，但损坏率仅有35%。三年后机器全部淘汰，购入新机器。应该如何安排生产（计划以一年为周期），使三年收入最多？ 分析：假设X1、Y1表示第一年时生产P1的机器台数和生产P2的机器台数，则X2，Y2，X3，Y3以此类推。可知： X1+Y1=1000 X2+Y2=0.35*X1+0.65*Y1 X3+Y3=0.35*X2+0.65*Y2 而三年的总收入为：Z=4500*（X1+X2+X3）+3500*（Y1+Y2+Y3） （1）设在第二年后还剩N台机器，则第三年的收入为： Z(3,N) =4500*X3+3500*Y3 =4500*X3+3500*（N-X3） =1000*X3+3500N 显然我们知道：0<=X3<=N，则Z3最大时，X3=N（Y3=0），此时， Zmax(3，N)=4500*N。 （2）设在第一年后还剩N台机器，则第二年后（最后两年）的收入为： Z（2，N）=4500*X2+3500*（N-X2）+Zmax(3, 0.35*X2+0.65*(N-X2)) =1000*X2+3500*N+4500*（0.65*N-0.3*X2） =（3500+2925）*N-（1350-1000）*X2 第 22 页 共 31页 中山纪念中学信息学奥林匹克算法设计题选 <=6425*N 显然，当X2=0，X3=0.65*N时，Z（2，N）取最大值。 （3）最后考虑整个三年的生产，设开始时有N台机器，则三年的收入总和为： Z（1，N）=4500*X1+3500（N-X1）+Zmax(2， 0.35*X1+0.65*(N-X1)) =1000*X1+3500*N+6425*（0.65*N-0.3*X1） =（3500+6425*0.65）*N-（0.3*6425-1000）*X1 <=（3500+6425*0.65）*N 综上所述，当X1=0，X2=0，X3=0.65*0.65*N时，收入取得最大值。即： 生产P1的机器台数 生产P2的机器台数 第1年 0 1000 第2年 0 650 第3年 422 0 此时三年收入最大。 5、动态规划：如下图是一个交通示意图，边上的数字表示路的长度。求每个点到V6的最短路径。 分析：先建立距离矩阵，D：0表示不通。 V1 V2 V3 V4 V5 V6 V1 0 3 5 0 0 0 V2 3 0 4 6 5 0 V3 5 4 0 4 3 0 V4 0 6 4 0 0 4 V5 0 5 3 0 0 5 V6 0 0 0 4 5 0 D（I，J）表示I点到J点的距离。 设L（I）为第I个点到V6的最短路径，则有：L（I）=min{(D(I,J)+L(J))} ，（I<>J）J为与I相通的所有的点。 如： L(6)=0 L(5)=min{(d(5,2)+L(2),(d(5,3)+L(3)),(d(5,6)+L(6))} =min{5+L(2), 3+L(3), 5+L(6)} L(4)=?? ?? 反复运算，直到L(1)--L(6)的值都不再改变为止。程序如下 uses crt; const d:array[1..6,1..6] of integer=((0,3,5,0,0,0), {距离矩阵} (3,0,4,6,5,0), (5,4,0,4,3,0), (0,6,4,0,0,4), (0,5,3,0,0,5), (0,0,0,4,5,0)); var l:array[1..6] of integer; {存放最短距离} i,j,m:integer; gb:boolean; {用来判断最短距离是否改变} begin clrscr; for i:=1 to 5 do l[i]:=10000; {先假设每个点到V6的最短距离很小} 第 23 页 共 31页 中山纪念中学信息学奥林匹克算法设计题选 l[6]:=0; {V6到V6的最短距离为0} repeat gb:=false; for i:=1 to 5 do begin {计算L（1）??L（5）} m:=1000; for j:=1 to 6 do begin {通过与第I个点相通的所有点中计算L（I）} if d[i,j]>0 then begin if d[i,j]+l[j] if m until not gb; {直到L（I）不再改变} for i:=1 to 6 do write(l[i]:4); end. 6、动态规划：某印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表（时间单位：天） 任务 J1 J2 J3 J4 J5 J6 印刷车间 3 12 5 2 9 11 装订车间 8 10 9 6 3 1 问应该如何安排加工顺序使加工时间最少。 7、动态规划：若有四项任务：J1，J2，J3，J4，要先后使用机器M1，M2，使用机器的时间见下表： 任务 J1 J2 J3 J4 机器M1 3 4 8 10 机器M2 5 2 9 15 问怎样安排才能使所花时间最短。 8、动态规划：求下面图中任一点到V10点的最短路径。 9、动态规划：N枚硬币C1，C2，C3??，CN（N由键盘输入）中有一块不合格，不合格的硬币较正常为重。现用一天平找出不合格的一块，要求在最坏的情况下，用的天平次数最少。 10、动态规划：预测某产品连续四个月的市场需求量依次为220，240，200，190件，相邻的前后两个月生产能力的改变要付出代价，其数值等于改变量平方的两倍。每月多生产的部分，每件产品要付出12单位的代价 第 24 页 共 31页 中山纪念中学信息学奥林匹克算法设计题选 把它们作废处理。若当月生产能力为200件，应如何合理地安排下面四个月的生产使效益最好。 11、动态规划：7万元投资到A、B、C三个项目上，其利润见下表： 投资额（万元） 1 2 3 4 5 6 7 A 0.11 0.13 0.15 0.24 0.24 0.30 0.35 B 0.12 0.16 0.21 0.25 0.25 0.29 0.34 C 0.08 0.12 0.20 0.26 0.26 0.30 0.35 问应如何分配投资额，使获得的利润最大。 十一、贪婪法 1、贪婪法：背包问题：假定有N个物体和一个背包，物体重量为Wi，价值Pi，而背包的载重能力为M。若将物体i的Xi部分（1<=i<=n,0<=Xi<=1）装入背包中，则有价值Pi*Xi，应怎样选择各种物体，使背包里所放的物体的总价值最高。 分析：这个问题如果只是把价值最高的物体优先放入包中的话，这显然是不对的，因为他没有考虑到物体的重量，所以我们应该把物体的单位价值计算出来，排序后按由大到小的顺序取物体，直到背包装满为止。这就是贪婪法，也就是得到最贪心的解。 2、贪婪法：如下图所示，一个正方形的四角分别放若干棋子，每一次可以从任一角去掉X枚棋子，同时在其余每一个角上添加X枚棋子。初始状态时角A上有一枚棋子，其余三角没有棋子。编程寻找一种方案，用最少的步数实现四个角从初始状态到目标状态的转换。目标状态从键盘输入（按A、B、C、D的顺序读入四个数字）。 A B D C 分析：我们将A、B、C、D四个角分别标号，用A1、A2、A3、A4分别表示初始状态，即初始状态为（A1、A2、A3、A4）；而用（D1、D2、D3、D4）来表示目标状态。 现在我们来看：如果把A1减少一枚棋子的话，其余三角就各增加一枚，各角增量可表示为E1=（-1，1，1，1）；同样的，其余各角的增量可分别表示为：E2=（1，-1，1，1）、E3=（1，1，-1，1）、E4=（1，1，1，-1）。 也就是说，从某个位置i取走X个棋子的增量变化为：X*Ei。并由此可得初始状态与目标状态的关系式：(A1，A2，A3，A4)+X1*E1+X2*E2+X3*E3+X4*E4 =(D1,D2,D3,D4) 即为以下四元一次方程： -X1+X2+X3+X4=D1-1 X1-X2+X3+X4=D2 X1+X2-X3+X4=D3 X1+X2+X3-X4=D4 解此方程，可得解： X1=(-D1+D2+D3+D4+1)/4 X2=(D1-D2+D3+D4-1)/4 X3=(D1+D2-D3+D4-1)/4 X4=(D1+D2+D3-D4-1)/4 若X1、X2、X3、X4全为正整数，则说明初始状态经过X1*E1，X2*E2，X3*E3，X4*E4的变化就可以达到目标状态。如果没有整数解呢？ 但有一点要注意的就是：当前的第i角的棋子数量Ai必须大于等于Xi时，才能进行第i角上移走Xi个棋子的操作。否则，就必须分几次操作。 为了使移棋子次数尽量少，我们应该尽量在棋子数量足够多的角上移走棋子，然后就不必在该角上移走棋子了（可用一数组存放每个角还要移走多少枚棋子）；而如果没有一个角的棋子足够多，我们就应该移棋子数最多的那个角，把该角的棋子全部移走，并且在存放各角还要移走棋子数量的数组中减去该角已经移走的棋子的数量。如此重复下去，直到数组中各数值为0，即目标状态实现时为止。 此题的贪婪所在就在于每次移走尽可能多的棋子。 第 25 页 共 31页