数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时装研究
法律研究使用动态规划执行最佳括号化排列的 C++ 程序
这是一个使用动态规划执行最佳括号化的 C++ 程序。
算法
Begin Take the length n and dimension of matrix as input. MatrixChain() to find out minimum multiplications: Arguments: a[i][j]=Minimum number of scalar multiplications needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where dimension of A[i] is p[i-1] x p[i]. a[i][j] means cost is zero when multiplying one matrix. L is chain length. m = cost / scalar multiplications. Body of the function: for i = 1 to n-1 Initialize a[i][i] = 0 for L = 2 to n-1 for i = 1 to n - L + 1 j = i + L - 1 a[i][j] = INT_MAX for k = i to j - 1 m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j]; if (m < a[i][j]) a[i][j] = m b[i][j] = k return a[1][n - 1] End
示例
#include<limits.h>
#include<iostream>
using namespace std;
int MatrixChain(int p[], int n) {
int a[n][n];
int b[n][n];
int i, j, k, L, m;
for (i = 1; i < n; i++)
a[i][i] = 0;
for (L = 2; L < n; L++) {
for (i = 1; i <= n - L + 1; i++) {
j = i + L - 1;
a[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++) {
m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
if (m < a[i][j]) {
a[i][j] = m;
b[i][j] = k;
}
}
}
}
return a[1][n - 1];
}
int main() {
cout << "Enter the length:";
int n;
cin >> n;
int a[n];
cout << "Enter the dimensions: ";
for (int v = 0; v < n; ++v) {
cin >> a[v];
}
cout << "Minimum number of multiplications is: " <<
MatrixChain(a,n);
return 0;
}输出
Enter the length:5 Enter the dimensions: 2 3 7 6 4 Minimum number of multiplications is: 174
更新于： 2019 年 7 月 30 日
150 次浏览
广告