实验三 动态规划算法.doc

实验三 动态规划算法一、 实验目的进一步理解动态规划算法的基本思想，掌握设计有效算法的动态规划方法，会使用动态规划解决一些实际问题。二、 实验要求1、上机前的准备工作根据实验内容中所给题目，利用所学动态规划算法的基本设计思想设计算法并编写好上机程序，以提高上机效率；2、独立上机，输入、调试所编程序；3、上机结束后，写出实验报告。4、上机时间：4学时三、 实验内容算法实现题：1、3-3#include using namespace std;const int N=4;int s2*N=0,3,4,2,1,3,4,2;/一共4堆石子，3,4,2,1int m2*N2*N;int h2*N2*N;int totalValue(int i,int j)int sum=0;for(int k=i;k=j;k+)sum+=sk;return sum;void maxsum(int n) /求最大值int i,j,r,k,t; for (i = 1; i = n; i+) mii = 0; for ( r = 2; r = n; r+) for ( i = 1; i n - r+1; i+) j=i+r-1; mij = mi+1j; hij=i; for ( k = i+1; k mij) mij = t; hij=k; mij+=totalValue(i,j); void minsum(int n)/求最小值int i,j,r,k,t; for (i = 1; i =n; i+) mii = 0; for ( r = 2; r = n; r+) for ( i = 1; i n - r+1; i+) j=i+r-1; mij = mi+1j; hij=i; for ( k = i+1; k j; k+) t = mik + mk+1j; if (tmij) mij = t; hij=k; mij+=totalValue(i,j); void Traceback(int i,int j,int h2*N)if(i=j)return;Traceback(i,hij,h); Traceback(hij+1,j,h);couti jendl;void main()int i,j,p,q,n=N;minsum(2*n);int min_result=m1n;p=1;q=n;for(i=2;imin-1+i)p=i;q=n-1+i;min_result=mpq; cout最小值：min_resultendl; Traceback(p,q,h); maxsum(2*n);int max_result=m1n;p=1;q=n;for(i=2;i=n;i+)if(max_result min-1+i)p=i;q=n-1+i;max_result=mpq;/coutp qendl;cout最大值：max_resultendl;Traceback(p,q,h);运行结果：2、3-4#include iostream.hvoid main( ) int a5050,data5050,b5050,i,j,n;coutn;for( i=1;i=n;i+)for(j=1;jdataij;/将数据放到二维数组aij=dataij;bij=0;for (i=n-1; i=1;i-)for(j=1;jai+1j+1) aij=aij+ai+1j;bij=0;else aij=aij+ai+1j+1;bij=1;coutmax=a11endl;j=1;for( i=1 ;i=n-1;i+) coutdataij;j=j+bij; coutdatanj;运行结果：3、3-6 #includeusing namespace std;const int N=4;int mN+1N+1=0,0,0,0,0,0,0,5,8,20,0,0,0,7,18,0,0,0,0,2,0,0,0,0,0; int hN+1N+1;/由矩阵连乘的算法void Boat(int n)int i,j,r,k,t; for (i = 1; i = n; i+) mii = 0; for ( r = 2; r = n; r+) for ( i = 1; i = n - r+1; i+) j=i+r-1; hij=i; for ( k = i+1; k j; k+) t = mik + mkj ; if (t mij) mij = t;hij=k; void Traceback(int i,int j,int hN+1)if(i=j)return;Traceback(i,hij,h); Traceback(hij+1,j,h);coutAi,hij和Ahij+1,jendl;void main()int n=N;Boat(n);Traceback(1,n,h);coutm1Nendl;运行结果：4、防卫导弹 一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。 现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的进攻导弹(这些导弹发射的间隔时间固定，飞行速度相同)，该防卫导弹所能获得的信息包括各个导弹的高度，以及它们发射次序。 现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： (1) 它是该次测试中第一个被防卫导弹截击的导弹。 (2)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。#includeusing namespace std;int h100=0; int n; int Plane() int i,j; int num101=0; int maxi,MAX; numn-1=1; for(i=n-2;i=0;i-) maxi=0; for(j=i+1;j=hj &numjmaxi) maxi=numj; numi=maxi+1; for(i=0;iMAX) MAX=numi; return MAX ;int main()int t=1;while(t=1)coutn;cout请输入导弹的高度：;for(int i=0;ihi; cout能捕获的导弹的个数：Plane()endl;int k=1;while(k)coutt;if(t=1)t=1;k=0;else if(t=2)t=0;k=0;else k=1; return 0;运行结果：5、资源分配问题某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的A、B、C三个工厂，各工厂在获得这种机器后，可以为国家盈利，如下表所示。问这5台机器如何分配给各工厂，才能使国家盈利最大？SABC000013542710639111141211125131112其中，第一列S为机器台数，A、B、C三列为3个工厂在拥有不同台数的机器时的盈利值。#include iostream.hvoid main( )int i,j,k,m,n,rest;int a100100,gain100;float q100,f100,temp100;coutm; coutn; cout请输入第1个项目的利润：endl; for( j=1;jqj; fj=qj;for( j=1;j=n;j+)a1j=j;for( k=2;k=m;k+) cout请输入第k项目的利润：endl; for( j=