ACM程序&算法

   算法設計 動態規劃 矩陣連乘問題 收藏

////////////////////////////////////////////////////////////////
//TITLE: 矩陣連乘問題
//EDITOR:小橋流水
//DADE： 2008.11.16
//TOOL:  Microsoft Visual Studio 2008
////////////////////////////////////////////////////////////////
 
#include<iostream>
usingnamespace std;
 
//計算最優值
voidMatrixChain(int *p,intn,int **m,int **s)
{
   for (inti = 1; i <= n;i++)
   {
       m[i][i] = 0;
   }
   for (intr = 2; r <= n;r++)
   {
       for (inti = 1;i <=n-r+1;i++)
       {
           int j = i+r-1;
           m[i][j] =m[i+1][j] +p[i-1]*p[i]*p[j];
           s[i][j] =i;
           for(intk = i+1;k <j;k++)
           {
               int t = m[i][k] + m[k+1][j] +p[i-1]*p[k]*p[j];
               if (t <m[i][j])
               {
                   m[i][j] =t;
                   s[i][j] =k;
               }
           }
       }
   }
}
 
//構造最優解
voidTraceback(inti,intj,int **s)
{
   if (i ==j)
       return ;
   Traceback(i,s[i][j],s);
   Traceback(s[i][j]+1,j,s);
   cout<<"Multiply A"<<i<<","<<s[i][j];
   cout<<"and A"<<s[i][j]+1<<","<<j<<endl;
}
 
intmain()
{
   int N,*P,**M,**S;
   cout<<"輸入矩陣的個數N: ";
   cin>>N;
   P = new int [N+1]; //為矩陣的維數分配空間
   M = new int *[N+1];//為二維數組M動態分配空間
   for (inti = 0; i <= N;i++)
   {
       M[i] =new int [N+1];
   }
   S = new int *[N+1]; //為記錄最優斷開位置的二
   //維數組S動態分配空間
   for (inti = 0; i <= N;i++)
   {
       S[i] =new int [N+1];
   }
 
   for (inti = 0; i <= N;i++)
   {
       cin>>P[i];
   }
  www.2cto.com
   MatrixChain(P,N,M,S);
   Traceback(1,N,S);
 
   //釋放動態分配的空間
   delete []P;
   for (inti = 0; i <=N;i++)
   {
       delete M[i];
       M[i] =NULL;
   }
   delete []M;
   M = NULL;
   for (inti = 0; i <=N;i++)
   {
       delete S[i];
       S[i] =NULL;
   }
   delete []S;
   S = NULL;
 
   return 0;
}