华东师范大学计算机科学技术系上机实践报告一、 内容与设计思想1．对于以下5 个矩阵：M 1: 2⨯3, M 2: 3⨯6, M 3: 6⨯4, M 4: 4⨯2, M 5: 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背包问题为：}x p max{n 1i i i ∑=。

限制条件为：c x w n 1i i i ≤∑=，且n i 1},2,1,0{x i ≤≤∈。

设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 ，0<n<=20,0<M<100000。

再下去的n 行每行有两个整数Wi 和Pi, 0<Wi,Pi<10000。

输出：对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。

)/4()(11)()(1)(2/311n n P n n k n P k P n P n n k Ω=⇒⎪⎩⎪⎨⎧>=-=∑-=我们保证输出的结果在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中的一条边时有i < j。

设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）完全加括号的矩阵连乘积#include<stdio.h>int p[51];__int64 m[51][51];int f(int n){int i,j,k;for(i=1;i<=n;i++)m[i][i]=0;for(k=1;k<n;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;j<i+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];}}return 0;}int main(){int N,n,i;scanf("%d",&N);while(N--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&p[i],&p[i+1]);f(n);printf("%I64d\n",m[1][n]);}}2）0-1背包问题#include<stdio.h>int w[25],v[25];int dp[100001];int main(){int n,m,N;int i,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++)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）最长路#include<stdio.h>int x[201][201];int main(){int i,j,k;int n,m;int a,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);}for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)for(k=i+1;k<j;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");else printf("%d\n",x[a][b]);}}}4）装箱问题#include<stdio.h>int w[31];int dp[20001];int main(){int n,N;int i,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）数塔#include<stdio.h>int a[101][101];int min[101][101];int main(){int N,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];else if(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];else min[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);}}。