写给自己的话:有时候虽然一道题懂做了,但是发现写解题报告时,要清楚把自己的思路描述出来却挺难的。做解题报告
不仅可以巩固、梳理知识,还可以加深理解。现在我还做得很不好, 一定要坚持! 加油!
矩阵链乘问题:
(下面第二个{P1应该是P2)
void MatrixChain()
{
int i, j, k, t;
for(i = 1; i <= n; i++)
m[i][i] = 0; //对角线赋值为0,是因为1个矩阵需做0次相乘
for(r=2; r<=n; ++r){
for(i=1; i<=n-r+1; ++i){
j=i+r-1;
dp[i][j] = INF; // INF表示一个很大的数
for(k=i; k<=j-1; ++k){
int temp=dp[i][k]+dp[k+1][j]+arr[i-1]*arr[k]*arr[j]; // arr数组的下标从0开始 。如果从1开始,各加1
if(temp<dp[i][j])
dp[i][j]=temp;
}
}
}
}
RQNOJ矩阵链乘法http://www.rqnoj.cn/Problem_652.html
题目描述
我们都知道矩阵乘法:给定两个矩阵A和B,若A是n*r的矩阵,B是r*m的矩阵,则A*B的结果C是一个n*m的矩阵,且c[i,j]=∑a[i,k]*b[k,j],其中1<=k<=r。很显然,求出每个C[i,j]的过程中,我们都做了r次标量乘法。因此,总的标量乘法次数是n*m*r。
矩阵乘法满足结合律。换句话说,即使乘的顺序不同,结果都是相同的。例如,四个矩阵<A1,A2,A3,A4>相乘,会有五种不同的顺序:
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
但是,不同的顺序会导致不同的效率——本题中,我们希望将给定的矩阵乘起来,并且使得总的标量乘法次数最少。注意,本题中给定的矩阵可以看作是环形的——第一个和最后一个矩阵可以相乘!为了满足矩阵乘法的合法性,输入数据保证对于任意相邻的矩阵,它们相邻的维数一定相等。
【数据规模和约定】
n<=100
所有矩阵的行、列数都是不超过1000的正整数。
输入格式
第一行一个整数n,表示矩阵个数。
接下来n行,每行两个整数,表示这个矩阵的行数和列数。
输出格式
一个整数,表示最少乘法次数。
4
2 3
3 5
5 10
10 2
样例输出
142
/*
这一题和另外一题《能量项链》完全相同。
注意这第一个矩阵可以和最后一个相连, 相当于是一个环
处理环时,把这个环断掉,变成一条线,然后复制元素增长
处理时,它有不同个起点。
分别比较每个起点的结果,取其中最小的就是答案
*/
#include<cstdio>
#include<cstring>
#define MAXN 250
#define INF 2147483646
int arr[MAXN];
int dp[MAXN][MAXN];
int main()
{
// freopen("input.txt","r",stdin);
int i,n,a,b,r,j,k,s;
scanf("%d",&n);
for(i=1; i<=n; ++i){
scanf("%d %d",&arr[i],&a);
arr[i+n]=arr[i]; // 复制元素
}
int ans=2147483646;
for(s=0; s<=n-1; ++s){ // 起点位置
memset(dp,0,sizeof(dp));
for(r=2; r<=n; ++r){
for(i=1; i<=n-r+1; ++i){
j=i+r-1;
dp[i][j]=INF;
for(k=i; k<=j-1; ++k){
int temp=dp[i][k]+dp[k+1][j]+arr[i+s]*arr[k+1+s]*arr[j+1+s];
if(temp<dp[i][j])
dp[i][j]=temp;
}
}
}
if(dp[1][n]<ans)
ans=dp[1][n];
}
printf("%d\n",ans);
return 0;
}
UVA 10003-Cutting
Sticks
/*
这题也是矩阵连乘问题
关键在于把砍木棍的过程逆过来看。
即现在不是砍,而是把n段不同长度的木棍连成一整段
每次两根木棍连接成一段时,这两根木棍的长度之和就是这次的费用。
*/
#include<cstdio>
#include<cstring>
#define MAXN 55
#define INF 2147483646
int len[MAXN],arr[MAXN];
int dp[MAXN][MAXN];
int main()
{
freopen("input.txt","r",stdin);
int l,n,i,j,k,r;
while(scanf("%d",&l),l){
scanf("%d",&n);
len[0] = 0, arr[0]=0;
for(i=1; i<=n; ++i){
scanf("%d",&arr[i]);
len[i] = arr[i]-arr[i-1];
}
arr[n+1]=l;
len[n+1] = l-arr[n];
memset(dp,0,sizeof(dp));
for(r=2; r<=n+1; ++r){
for(i=1; i<=n+1-r+1; ++i){
j=r+i-1;
dp[i][j] = INF;
for(k=i; k<=j-1; ++k){
int temp=dp[i][k]+dp[k+1][j]+arr[j]-arr[i-1];
if(temp<dp[i][j])
dp[i][j] = temp;
}
}
}
printf("The minimum cutting is %d.\n",dp[1][n+1]);
}
return 0;
}
/*
[NOI1995] 石子合并
这题和上一题的木棍本质上都是一样的,只是石堆的放置是环状的。
处理一下把环状变成链状就可以了
然后比较各个不同起点得到答案
*/
#include<cstdio>
#include<cstring>
#define MAXN 105
#define oo 1147483646
int arr[MAXN];
int dp_min[MAXN][MAXN];
int dp_max[MAXN][MAXN];
inline int sum(int start,int end){
int sum=0;
for(int i=start; i<=end; ++i)
sum += arr[i];
return sum;
}
int main()
{
// freopen("input.txt","r",stdin);
int N,i,j,s,k,r;
while(scanf("%d",&N)!=EOF){
for(i=1; i<=N; ++i){
scanf("%d",&arr[i]);
arr[i+N]=arr[i];
}
memset(dp_min,0,sizeof(dp_min));
memset(dp_max,0,sizeof(dp_max));
int ans1=oo, ans2=-oo;
for(s=0; s<=N-1; ++s){
for(r=2; r<=N+1; ++r){
for(i=1; i<=N-r+1; ++i){
j=r+i-1;
dp_min[i][j] = oo;
dp_max[i][j] = -oo;
int total=sum(i+s,j+s);
for(k=i; k<=j-1; ++k){
int t1=dp_min[i][k]+dp_min[k+1][j]+total;
int t2=dp_max[i][k]+dp_max[k+1][j]+total;
if(t1<dp_min[i][j]) dp_min[i][j]=t1;
if(t2>dp_max[i][j]) dp_max[i][j]=t2;
}
}
}
if(dp_min[1][N]<ans1) ans1=dp_min[1][N];
if(dp_max[1][N]>ans2) ans2=dp_max[1][N];
}
printf("%d\n%d\n",ans1,ans2);
}
return 0;
}
/*
UVa 348 Optimal Array Multiplication Sequence
矩阵连乘 + 打印
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 15
#define INF 1073741824
int m[MAXN];
int dp[MAXN][MAXN],s[MAXN][MAXN];
// 递归打印
void Print(int i,int j){
if(i==j){
printf("A%d",i);
return ;
}
else{
printf("(");
Print(i,s[i][j]);
printf(" x ");
Print(s[i][j]+1,j);
printf(")");
}
}
int main()
{
freopen("input.txt","r",stdin);
int n,r,b,i,j,k,cas=1;
while(scanf("%d",&n)!=EOF){
if(!n) break;
printf("Case %d: ",cas++);
for(i=0; i<n; ++i)
scanf("%d%d",&m[i],&b);
m[n]=b;
memset(dp,0,sizeof(dp));
memset(s,0,sizeof(s));
for(r=2; r<=n; ++r){
for(i=1; i<=n-r+1; ++i){
j=i+r-1;
dp[i][j]=INF;
s[i][j]=i;
for(k=i; k<=j-1; ++k){
int temp=dp[i][k]+dp[k+1][j]+m[i-1]*m[k]*m[j];
if(temp<dp[i][j])
dp[i][j]=temp, s[i][j]=k;
}
}
}
Print(1,n);
printf("\n");
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
c++实现矩阵连乘问题,通过动态规划法的思想求得。
动态规划方法解决矩阵连乘问题,即寻求多个矩阵连乘时的最好的加括号方式使得总的乘法两最小; 可以设定矩阵个数,手动输入矩阵的阶,显示动态规划算法的表格,即乘法量和括号信息; 多文档,C++6.0
算法设计与分析,使用动态规划法解决矩阵连乘问题。内有MatrixChain、TraceBack、RecurMatrixChain-递归解决矩阵连乘问题等程序,非常超值啊!
主要介绍了Java矩阵连乘问题(动态规划)算法,结合实例形式分析了java实现矩阵连乘的算法原理与相关实现技巧,需要的朋友可以参考下
矩阵连乘问题算法描述 矩阵连乘问题的算法实现 矩阵连乘问题的算法实现
c/c++语言解决矩阵连乘文题,几个矩阵相乘求最佳结合顺序
矩阵连乘问题分析和实现用于动态规划 最佳加括号方式-动态规划算法
用Java来解决算法 矩阵连乘问题。实例6个二维矩阵相乘,求找到最优计算次序。
如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试...
动态规划思想的介绍(矩阵连乘问题,最长公共子序列,流水线作业调度问题,0-1背包问题)。算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
实现计算多个矩阵连乘的最终结果并且对时间复杂度进行了优化
算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
用动态规划思想解决矩阵连乘的问题。………………………………
【问题描述】使用动态规划算法解矩阵连乘问题,具体来说就是,依据其递归式自底向上的方式进行计算,在计算过程中,保存已子问题答案,每个子问题只解决一次,在后面计算需要时只要简单查一下得到其结果,从而避免...
详细叙述了矩阵连乘的法则,解释的清楚。而且有算法实现,真的是不错的东东