动态规划实验报告.doc

华东师范大学计算机科学技术系上机实践报告
内容与设计思想
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)，,b之间没连通，输出－1。
基本思想：
Floyd算法。时间复杂度是O(n^3).
4． 【装箱问题】：有一个箱子容量为V（正整数，0≤V≤20000），同时有 Ｎ个物品（0<Ｎ≤30），每个物品有一个体积（正整数）。要求从Ｎ个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入：
输入有多组测试数据，第一行一个正整数V,表示箱子的容量
第二行一个数据n表示物品个数。
第三行有n个数据，描述每个物品的体积
输出：
每个输出占一行，输