田忌赛马问题

郭佳奇：动态规划与数学软件的实现1田忌赛马问题一问题描述田忌与齐王赛马，双方各有n匹马参赛（n=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。算法思想先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：若田忌的马快，就让这两匹马比赛；若田忌的马慢，干脆就让他对付齐王最快的马；若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。则：时当时＝当时当]1[]1[)1,1(]1[]1[)}1,(),1,1(max{]1[]1[)1,(),(jbjiajiljbjiajiljiljbjiajiljil程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。二程序源代码#includestdio.hvoidreaddata();voidinit();intN,n,a[100],b[100],l[100][100];voidmain(){inti,j,k;scanf(%d,&N);//测试例子得个数for(k=0;kN;k++){readdata();init();for(i=n-2;i=0;i--)for(j=1;jn-i;j++)if(a[i+j]b[j])l[i][j]=l[i][j-1]+1;elseif(a[i+j]b[j])l[i][j]=l[i+1][j-1]-1;elseif(l[i+1][j-1]-1l[i][j-1])l[i][j]=l[i+1][j-1]-1;运筹学上机报告2elsel[i][j]=l[i][j-1];printf(%d\n,l[0][n-1]);}}voidreaddata(){inti;scanf(%d,&n);//马的个数：-for(i=0;in;i++)scanf(%d,&a[i]);//每只马的速度；for(i=0;in;i++)scanf(%d,&b[i]);//每只马的速度；}int*qsort(inta[100],intn)//对输入的马的速度的无序序列进行排序{inti,j,t;for(i=0;in;i++)for(j=i+1;jn;j++)if(a[i]a[j]){t=a[i];a[i]=a[j];a[j]=t;}//for(i=0;in;i++)//printf(%3d,a[i]);//printf(\n);returna;}voidinit(){inti;qsort(a,n);qsort(b,n);for(i=0;in;i++){if(a[i]b[0])l[i][0]=1;elseif(a[i]==b[0])l[i][0]=0;elsel[i][0]=-1;}}三动态规划的求解方法做出总结用动态规划解决多阶段决策问题效率是很高的，而且思路清晰简便，同时易于实现，虽