㈠ 動態規劃 矩陣連乘 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