㈠ 动态规划 矩阵连乘 c语言
#include <stdio.h>
#include <limits.h>
#include<stdlib.h>
#define LENGTH 6
void MatrixChainOrder(int p[],int m[][LENGTH],int s[][LENGTH])
{
int n=LENGTH;
int i,j,k,r,t;
for(i=0;i<n;i++)
m[i][i]=0;
for( r=1;r<n;r++)
{
for(i=0;i<n-r;i++)
{
j=i+r;
m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1];
s[i][j]=i;
for(k=i+1;k<j;k++)
{
t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
printf("t=%d;,m[%d][%d]=%d\n",t,i,j,m[i][j]);
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
int main()
{
int p[] = {30,35,15,5,10,20,25};
int m[LENGTH][LENGTH];
int s[LENGTH][LENGTH];
int i,j,k;
MatrixChainOrder(p,m,s);
printf("最少数乘次数：\n");
for(i = 0;i<LENGTH;i++)
{ for(j = 0 ;j<=i ;j++ )
printf(" ");
for(k = i; k<LENGTH;k++)
printf("%8d",m[i][k]);
printf("\n");
}
printf("断开位置：\n");
for(i = 0;i<LENGTH;i++)
{ for(j = 0 ;j<=i ;j++ )
printf(" ");
for(k = i; k<LENGTH;k++)
printf("%4d",s[i][k]);
printf("\n");
}
system("Pause");
return 0;
}
㈡ C++有关矩阵连乘问题问题
#include<iostream.h>
#include<iomanip.h>
void MatrixChain(int *p,int n)
{
//动态分配二维数组
int **a,**s;
a=new int* [n];
s=new int* [n];
for(int i=0;i<n+1;i++) {s[i]=new int[n];a[i]=new int[n];}
//进行矩阵乘法
for(i=1;i<n+1;i++) a[i][i]=0;
for(i=2;i<n+1;i++)
for(int j=1;j<n-i+2;j++)
{
int r=j+i-1;
a[j][r]=a[j+1][r]+p[j-1]*p[j]*p[r];
s[j][r]=j;
for(int k=j+1;j<r;j++)
{
int temp=a[j][k]+a[k][r]+p[j-1]*p[k]*p[r];
if(temp<a[j][r])
{a[j][r]=temp;s[j][r]=k;}
}
}
//输出最优的算法步骤
for(i=1;i<n+1;i++)
{ for(int j=1;j<n+1;j++)
cout<<setw(8)<<a[i][j];
cout<<endl;
}
//最优的断开位置
for(i=1;i<n+1;i++)
{ for(int j=1;j<n+1;j++)
cout<<setw(4)<<s[i][j];
cout<<endl;
}
//删除动态分配的空间
for(i=0;i<n+1;i++)
{ delete []a[i];delete []s[i]; }
delete []p;delete []s;
}
void main()
{
}
㈢ 动态规划矩阵连乘问题
可怜，100分还没人理你，给我吧。
动态规划问题可以有tD/eD的形式，n^t为问题的大小，n^e为问题所依赖的子问题的大小
1D/1D型，最长上升子序列
2D/0D型，最长公共子序列
2D/1D型，多源最短路径
2D/2D型，双背包问题
当然可以有3D/1D或者更高的。
动态规划题目千变万化，主要是要学会思考方法，要能看到题目很快找出题目中的状态，找准状态后就基本没有难度了
㈣ 用动态规划方法求【矩阵连乘】最小次序的程序
您好吗，这样的：
#include<iostream> using namespace std;
const int MAX = 100;
//p用来记录矩阵的行列，main函数中有说明
//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解 //s[][]用来记录从哪里断开的才可得到该最优解 int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
int n;//矩阵个数
int matrixChain() {
for(int i=0;i<=n;i++) m[i][i]=0;
for(int r=2;r<=n;r++)//对角线循环 for(int i=0;i<=n-r;i++)//行循环 {
int j = r+i-1;//列的控制
//找m[i][j]的最小值，先初始化一下，令k=i m[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j +1]; s[i][j]=i;
//k从i+1到j-1循环找m[i][j]的最小值 for(int k = i+1;k<j;k++) {
int temp=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if(temp<m[i][j]) {
m[i][j]=temp;
//s[][]用来记录在子序列i-j段中，在k位置处 //断开能得到最优解 s[i][j]=k; } } }
return m[0][n-1]; }
//根据s[][]记录的各个子段的最优解，将其输出 void traceback(int i,int j) {
if(i==j) {
cout<<'A'<<i; return
}
if(i<s[i][j]) cout<<'(';
traceback(i,s[i][j]); if(i<s[i][j]) cout<<')'; if(s[i][j]+1<j) cout<<'(';
traceback(s[i][j]+1,j); if(s[i][j]+1<j) cout<<')'; }
void traceback(){ cout<<'(';
traceback(0,n-1); cout<<')'; cout<<endl; }
int main() {
cout<<"请输入矩阵的个数："<<endl; cin>>n;
cout<<"输入矩阵（形如a*b,中间用空格隔开）:"<<endl; for(int i=0;i<=n;i++) cin>>p[i];
//测试数据可以设为六个矩阵分别为
//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25] //则p[0-6]={30,35,15,5,10,20,25} cout<<"输出结果如下："<<endl; matrixChain();
traceback(0,n-1);
//最终解值为m[0][n-1]; cout<<endl; return 0;
}
㈤ 自己用C语言写了一个动态规划求矩阵连乘。但是在定义数组有问题。请高手指点。。
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];这句话调用到m[n][n],但是实际上只能调用到m[n-1][n-1]。（因为从0开始的嘛。不过有时候也能用，就是用了下一维的第0个）
所以要写int m[7][7]（要不就8，8）。
至于int m[n][n]为什么会对，我猜是直接用了内存的其他部分吧。。
㈥ 怎么算矩阵连乘
矩阵连乘的优化在算法里面 可以用动态规划解决。
因为矩阵连乘具有可结合性，因此，不同的运算次序（结合次序）花费的计算量是不一样的。
ABCD=A(BC)D=(AB)(CD)。而算法里面矩阵连乘问题的定义就是，给定矩阵（规模很大），确定运算次序，是总计算量最小。
dp[1][n]=min(dp[1][k]*dp[k+1][n]+w(k,k+1))(1<=k<n)。
不知楼主所谓的矩阵连乘是指哪一方面的。
㈦ 动态规划之矩阵连乘问题
矩阵连乘问题：设M1 M2 M3 ... Mn 为n个矩阵序列，其中Mi为 r[i] * r[i+1]阶矩阵，i=1,2,3 ... n。这个矩阵链的输入是向量 R=<r[0],r[1],[2]...r[n]>,因为矩阵运算满足结合律，所以运算结果与计算顺序无关，但是不同运算顺序，会造成运算时的乘法次数的不同。
求以哪种乘法次序运算，使得基本运算的总次数最少
举个栗子:
M1[5 * 20] * M2[20 * 50] * M3[50 * 1] * M4[1 100]
可能的运算次序有多种,如:
1. ((M1[5 * 20] * M2[20 * 50]) * M3[50 * 1]) * M4[1 100]
2. M1[5 * 20] * (M2[20 * 50] * (M3[50 * 1] * M4[1 100]))
3. (M1[5 * 20] * (M2[20 * 50] * M3[50 * 1])) * M4[1 100]
㈧ 矩阵链相乘问题 来个C#写的或C/C++写的
#include<stdio.h>
#include<stdlib.h>
#defineMAXN1000000
voidMatrix_Chain_Order(int*p,int*s,intN)
{
intn=N-1;
intm[N][N];
for(inti=1;i<=n;i++)
{
m[i][i]=0;
}
for(intl=2;l<=n;l++)/*lÊÇÁ´µÄ³¤¶È*/
{
for(inti=1;i<=n-l+1;i++)
{
intj=i+l-1;
m[i][j]=MAXN;
intq;
for(intk=i;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
*(s+i*N+j)=k;
}
}
}
}
}
voidPrint_Optimal_Parens(int*s,inti,intj,intN)
{
if(i==j)
{
printf("A%d",i);
}
else
{
printf("(");
Print_Optimal_Parens((int*)s,i,*(s+i*N+j),N);
Print_Optimal_Parens((int*)s,*(s+i*N+j)+1,j,N);
printf(")");
}
}
intmain()
{
intP[7]={30,35,15,5,10,20,25};
intS[7][7];
Matrix_Chain_Order(P,(int*)S,7);
Print_Optimal_Parens((int*)S,1,6,7);
system("pause");
return0;
}
这是我以前实现矩阵链相乘的算法，不符合你最终的显示，你稍微改一下就好
㈨ 贪心算法球矩阵连乘
我觉得不能用贪心法的，我们计算智能的老师也讲过，贪心是局部最优，而矩阵连乘问题不具备贪心选择性质，看过的相关资料也没能用贪心法成功解决。
㈩ 动态规划如何去找动态转移方程
1、最长公共子串
假设两个字符串为str1和str2，它们的长度分别为n和m。d[i][j]表示str1中前i个字符与str2中前j个字符分别组成的两个前缀字符串的最长公共长度。这样就把长度为n的str1和长度为m的str2划分成长度为i和长度为j的子问题进行求解。状态转移方程如下：
dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])
dp[i][j] = 0; (str1[i] != str2[j])
因为最长公共子串要求必须在原串中是连续的，所以一但某处出现不匹配的情况，此处的值就重置为0。
详细代码请看最长公共子串。
2、最长公共子序列
区分一下，最长公共子序列不同于最长公共子串，序列是保持子序列字符串的下标在str1和str2中的下标顺序是递增的，该字符串在原串中并不一定是连续的。同样的我们可以假设dp[i][j]表示为字符串str1的前i个字符和字符串str2的前j个字符的最长公共子序列的长度。状态转移方程如下：
dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])
dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1])
详细代码请看最长公共子序列。
3、最长递增子序列（最长递减子序列）
因为两者的思路都是一样的，所以只给出最长递减子序列的状态转移方程。假设有序列{a1,a2,...,an}，我们求其最长递增子序列长度。按照递推求解的思想，我们用F[i]代表若递增子序列以ai结束时它的最长长度。当 i 较小，我们容易直接得出其值，如 F[1] = 1。那么，如何由已经求得的 F[i]值推得后面的值呢？假设，F[1]到F[x-1]的值都已经确定，注意到，以ax 结尾的递增子序列，除了长度为1的情况，其它情况中，ax都是紧跟在一个由 ai(i < x)组成递增子序列之后。要求以ax结尾的最长递增子序列长度，我们依次比较 ax 与其之前所有的 ai(i < x)， 若ai小于 ax，则说明ax可以跟在以ai结尾的递增子序列之后，形成一个新的递 增子序列。又因为以ai结尾的递增子序列最长长度已经求得，那么在这种情况下，由以 ai 结尾的最长递增子序列再加上 ax 得到的新的序列，其长度也可以确定，取所有这些长度的最大值，我们即能得到 F[x]的值。特殊的，当没有ai(i < x)小 于ax， 那么以 ax 结尾的递增子序列最长长度为1。 即F[x] = max{1,F[i]+1|ai<ax && i<x}。
详细代码请看最长递增子序列。
4、最大子序列和的问题
假设有序列{a1,a2,...,an}，求子序列的和最大问题，我们用dp[i]表示以ai结尾的子序列的最大和。
dp[1] = a1; (a1>=0 && i == 1)
dp[i] = dp[i-1]+ai; (ai>=0 && i>=2)
dp[i] = 0; (dp[i-1] + ai <=0 && i>=2)
详细代码请看最大子序列的和。
5、数塔问题（动态搜索）
给定一个数组data[n][m]构成一个数塔求从最上面走到最低端经过的路径和最大。可以假设dp[i][j]表示走到第i行第j列位置处的最大值，那么可以推出状态转移方程：
dp[i][j] = max{dp[i-1][j-1],dp[i-1][j]} + data[i][j];
View Code
6、（01）背包问题
这是一个经典的动态规划问题，另外在贪心算法里也有背包问题，至于二者的区别在此就不做介绍了。
假设有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是c[i]，将哪些物品装入背包可使价值总和最大？
每一种物品都有两种可能即放入背包或者不放入背包。可以用dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值，则状态转移方程可以推出如下：
dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]};
View Code
可以参照动态规划 - 0-1背包问题的算法优化、动态规划-完全背包问题、动态规划-多重背包问题
7、矩阵连乘（矩阵链问题）-参考《算法导论》
例如矩阵链<A1,A2,A3>,它们的维数分别为10*100,100*5,5*50，那么如果顺序相乘即((A1A2)A3)，共需10*100*5 + 10*5*50 = 7500次乘法，如果按照(A1(A2A3))顺序相乘，却需做100*5*50 + 10*100*50 = 75000次乘法。两者之间相差了10倍，所以说矩阵链的相乘顺序也决定了计算量的大小。
我们用利用动态规划的方式(dp[i][j]表示第i个矩阵至第j个矩阵这段的最优解,还有对于两个矩阵A(i,j)*B(j,k)则需要i*j*k次乘法)，推出状态转移方程：
dp[i][j] = 0; (i ==j，表示只有一个矩阵，计算次数为0)
dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]}; (i<j && i<=k<j)
dp[1][n]即为最终求解.
View Code