动态规划实验报告
时间：2020-09-26 16:18:04 来源：勤学考试网 本文已影响 人 
华东师范大学计算机科学技术系上机实践报告
内容与设计思想
1．对于以下5 个矩阵：
M1: 2?3, M2: 3?6, M3: 6?4, M4: 4?2, M5: 2?7 ,
找出这5个矩阵相乘需要的最小数量乘法的次数。
请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。
输入：
第一行为正整数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背包问题为：。限制条件为：，且。设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。
输出：
对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。
我们保证输出的结果在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++)
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）最长路
#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);
x[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);
}
}
