动态规划实验报告

华东师范大学计算机科学技术系上机实践报告一、内容与设计思想1．对于以下5个矩阵：M1:23,M2:36,M3:64,M4:42,M5:27,(a)找出这5个矩阵相乘需要的最小数量乘法的次数。(b)请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。输入：第一行为正整数N,表示有N组测试数据；每组测试数据的第一行为n,表示有n个矩阵,2=n=50；接下去的n行,每行有两个整数x和y,表示第ni个矩阵是x*y的。输出：对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。我们保证输出的结果在2^64之内。基本思想：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：2．定义0/1/2背包问题为：}xpmax{n1iii。限制条件为：cxwn1iii，且ni1},2,1,0{xi。设f(i,y)表示剩余容量为y，剩余物品为：i，i+1，…，n时的最优解的值。1．）给出f(i,y)的递推表达式；2．）请设计求解f(i,y)的算法，并实现你的算法；3．）设W=[10,20,15,30]，P=[6,10,15,18],c=48，请用你的算法求解。输入：第一行为一个正整数N，表示有几组测试数据。每组测试数据的第一行为两个整数n和M，0n=20,0M100000。再下去的n行每行有两个整数Wi和Pi,0Wi,Pi10000。输出：对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。)/4()(11)()(1)(2/311nnPnnknPkPnPnnk我们保证输出的结果在2^64之内。基本思想：对第i个物品代价w，价值v，for(i=1;i=n;i++)for(j=m;j=w[i];j--)if(dp[j]dp[j-w[i]]+v[i])dp[j]=dp[j-w[i]]+v[i];3．设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当i，j为G中的一条边时有ij。设w(i，j)为边i，j的长度，请设计动态规划算法，计算图G中最长路径。并分析算法的时间复杂性。输入：输入一个数n(1=n=200)，表示有n个点，接下来一个数m，表示有m条路，接下来m行中每行输入2个数a，b，v表示从a点到b点有条路，路的长度为v。接下来输入一个数p，表示有p次询问，在接下来的p行中每行输入2个数a,b，算出此图中从a到b的最长路径。输出：对每个询问p，(a,b)，输出从a到b之间的最长路.如果a,b之间没连通，输出－1。基本思想：Floyd算法。时间复杂度是O(n^3).4．【装箱问题】：有一个箱子容量为V（正整数，0≤V≤20000），同时有Ｎ个物品（0Ｎ≤30），每个物品有一个体积（正整数）。要求从Ｎ个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入：输入有多组测试数据，第一行一个正整数V,表示箱子的容量第二行一个数据n表示物品个数。第三行有n个数据，描述每个物品的体积输出：每个输出占一行，输出箱子最后剩下的最小体积基本思想：类似0-1背包问题，弄成0-1背包的反面，看0-1背包那些值可以达到，再用n减去离他最近的比他小的值即为所得。5．【数字三角形】：给定一个具有Ｎ层的数学三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分及相应路径。输入：输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1=N=100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。输出：对于每个测试实例，输出可能得到的最小和。并在下一行输出路径。基本思想：从上往下遍历，每一层每一个数都记录从1到它的最小值，最后从最后一层中找出最小数即可。二、调试过程三、附录1）完全加括号的矩阵连乘积#includestdio.hintp[51];__int64m[51][51];intf(intn){inti,j,k;for(i=1;i=n;i++)m[i][i]=0;for(k=1;kn;k++)for(i=1;i=n-k;i++){m[i][i+k]=m[i][i]+m[i+1][i+k]+p[i-1]*p[i]*p[i+k];for(j=i+1;ji+k;j++){if(m[i][i+k]m[i][j]+m[j+1][i+k]+p[i-1]*p[j]*p[i+k])m[i][i+k]=m[i][j]+m[j+1][i+k]+p[i-1]*p[j]*p[i+k];}}return0;}intmain(){intN,n,i;scanf(%d,&N);while(N--){scanf(%d,&n);for(i=0;in;i++)scanf(%d%d,&p[i],&p[i+1]);f(n);printf(%I64d\n,m[1][n]);}}2）0-1背包问题#includestdio.hintw[25],v[25];intdp[100001];intmain(){intn,m,N;inti,j;scanf(%d,&N);while(N--){scanf(%d%d,&n,&m);for(i=1;i=n;i++)scanf(%d%d,&w[i],&v[i]);for(i=1;i=m;i++)dp[i]=0;for(i=1;i=n;i++)for(j=m;j=w[i];j--)if(dp[j]dp[j-w[i]]+v[i])dp[j]=dp[j-w[i]]+v[i];printf(%d\n,dp[m]);}}3）最长路#includestdio.hintx[201][201];intmain(){inti,j,k;intn,m;inta,b,v,p;while(scanf(%d%d,&n,&m)!=EOF){for(i=1;i=n;i++)for(j=1;j=n;j++)x[i][j]=0;for(i=1;i=m;i++){scanf(%d%d%d,&a,&b,&v);x[a][b]=v;}for(i=1;i=n;i++)for(j=i+1;j=n;j++)for(k=i+1;kj;k++)if(x[i][k]+x[k][j]x[i][j])x[i][j]=x[i][k]+x[k][j];scanf(%d,&p);while(p--){scanf(%d%d,&a,&b);if(x[a][b]==0)printf(-1\n);elseprintf(%d\n,x[a][b]);}}}4）装箱问题#includestdio.hintw[31];intdp[20001];intmain(){intn,N;inti,j;while(scanf(%d,&N)!=EOF){scanf(%d,&n);for(i=1;i=n;i++)scanf(%d,&w[i]);for(i=0;i=N;i++)dp[i]=0;dp[0]=1;for(i=1;i=n;i++)for(j=N;j=0;j--)if(dp[j]==1&&(j+w[i])=N)dp[j+w[i]]=1;for(i=N;dp[i]==0;i--);printf(%d\n,N-i);}}5）数塔#includestdio.hinta[101][101];intmin[101][101];intmain(){intN,n,i,j,x;scanf(%d,&N);while(N--){scanf(%d,&n);for(i=1;i=n;i++)for(j=1;j=i;j++)scanf(%d,&a[i][j]);min[1][1]=a[1][1];for(i=2;i=n;i++)for(j=1;j=i;j++){if(j==1)min[i][j]=min[i-1][j]+a[i][j];elseif(j==i)min[i][j]=min[i-1][j-1]+a[i][j];else{if(min[i-1][j]min[i-1][j-1])min[i][j]=min[i-1][j-1]+a[i][j];elsemin[i][j]=min[i-1][j]+a[i][j];}}x=min[n][1];for(i=2;i=n;i++)if(min[n][i]x)x=min[n][i];printf(%d\n,x);}}