下载文档原格式
运筹学论文——“田忌赛马”问题分析及启示选题背景：在中国战国时期，曾经有过一次流传后世的赛马比赛，相信大家都知道，这就是田忌赛马。
田忌赛马的故事说明在已有的条件下，经过筹划，选择一个最好的方案，就会取得最好的效果。
是现代运筹学的典型案例。
其主要是在研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。
当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。
运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，已达到最好的效果。
为此，我们想通过进一步的分析田忌赛马问题，展示运筹学在现实生活和决策中的重要地位。
让大家更好地了解和运用运筹学的思想进行生产和生活。
问题描述：《史记》中有这样一个故事：有一天，齐王要田忌和他赛马，规定每个人从自己的上、中、下三等马中各选一匹来赛；并规定，每次拿一匹马来比赛；并约定，每有一匹马取胜可获千两黄金，每有一匹马落后要付千两黄金。
当时，齐王的每一等次的马比田忌同样等次的马都要强，因而，如果田忌用自己的上等马与齐王的上等马比，用自己的中等马与齐王的中等马比，用自己的下等马与齐王的下等马比，则田忌要输三次，因而要输黄金三千两。
但是结果，田忌没有输，反而赢了一千两黄金。
这是怎么回事呢？答案早已经不是秘密，而其内在的思想去值得我们学习和研究。
在赛马之前，田忌的谋士孙膑给他出了一个主意，让田忌用自己的下等马去与齐王的上等马比，用自己的上等马与齐王的中等马比，用自己的中等马与齐王的下等马比。
田忌的下等马当然会输，但是上等马和中等马都赢了。
因而田忌不仅没有输掉黄金三千两，还赢了黄金一千两。
分析与求解：通过深入的分析，其实我们可以看到田忌赛马能够赢并不是必然的，是有一些必要因素存在的。
下面是我给出的分析：首先，假设田忌为X方，齐王为Y方。
田忌有上中下三种马匹，按其速度分别记为X1,X2,X3;齐王也有上中下三种马匹，按其速度分别记为Y1,Y2,Y3;其中，X1 > X2> X3 ; Y1 > Y2 > Y3;则由故事中所述容易得出：Y1 > X1 ；Y2 > X2 ；Y3 > X3一，不做任何的调整胜负我们是以三局两胜制进行判定的，由此可得出如下对田忌局势的分析表格:双方场次1 2 3 结果齐王Y1Y1>X1负Y2Y2>X2负Y3Y3>X3负田忌X1X1X3 负所以，可轻易得出田忌必败。
田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。
分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。
本问题应用的算法是动态规划和贪心算法相结合解决的。
从两人的最弱的马入手：若田忌的马快，就让这两匹马比赛；若田忌的马慢，干脆就让他对付齐王最快的马；若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。
定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。
则：程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。
初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。
程序如下：#include<stdio.h>void readdata();void init();int n,a[100],b[100],l[100][100];int main(){int i,j;readdata();init();for(i=n-2;i>=0;i--)for(j=1;j<n-i;j++)if(a[i+j]<b[j])l[i][j]=l[i][j-1]+1;else if(a[i+j]>b[j])l[i][j]=l[i+1][j-1]-1;else if(l[i+1][j-1]-1>l[i][j-1])l[i][j]=l[i+1][j-1]-1;elsel[i][j]=l[i][j-1];printf("%d",l[0][n-1]);}void readdata(){int i;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)scanf("%d",&b[i]);}void init(){int i;// qsort(a,n); //略for(i=0;i<n;i++){if(a[i]<b[0])l[i][0]=1;else if(a[i]==b[0])l[i][0]=0;elsel[i][0]=-1;}}输入：多个测例。
