精选优质文档-倾情为你奉上华东师范大学计算机科学技术系上机实践报告一、 内容与设计思想1对于以下5 个矩阵：M1: 23, M2: 36, M3: 64, M4: 42, M5: 27 ,(a) 找出这5个矩阵相乘需要的最小数量乘法的次数。(b) 请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。输入：第一行为正整数N,表示有N组测试数据；每组测试数据的第一行为n,表示有n个矩阵,2=n=50；接下去的n行,每行有两个整数x和y,表示第ni个矩阵是x*y的。输出：对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。我们保证输出的结果在264之内。基本思想：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：2定义0/1/2背包问题为：。限制条件为：，且。设f(i , y)表示剩余容量为y，剩余物品为：i，i+1，n时的最优
