Matrix Chain Optimal
karpar
posted @ 2008年10月20日 00:27
in
Algorithm
with tags
maxtrix chain.optimal
, 1204 阅读
-
#include <iostream>
-
#include <cstdlib>
-
using namespace std;
-
-
#define MAX 32767
-
-
void MatrixChainOrder(int *p)
-
{
-
int n = 6; int q;
-
int m[6][6];
-
for (int i = 0; i < n; i++)
-
m[i][i] = 0; // lowest layer's value is 0
-
for (int l = 2; l <= n; l++) // l is the chain length.
-
for (int i = 0; i < n - l + 1; i++) {
-
int j = i + l - 1;
-
m[i][j] = MAX;
-
for (int k = i; k <= j - 1; k++) {
-
q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
-
if (q < m[i][j])
-
m[i][j] = q;
-
}
-
}
-
cout << m[1][4] << endl;
-
}
-
-
int main()
-
{
-
int p[7] = {30, 35, 15, 5, 10, 20, 25};
-
MatrixChainOrder(p);
-
return 0;
-
}
评论 (0)