经典例题-MatrixChain

MatrixChain

We have a sequense continues matrix and A of matrix's col equals B of matrix's row.
When the A of matrix multiply B，the operate times is row[A] * col[A] * col[B].
So, please to calculate minmal operate times, if you change matrix multiply order.

Sample

#include <iostream>
using namespace std;
#include <time.h>
#include <stdlib.h>
#include <string.h>
int const MAX_DATA = 60, MIN_DATA = 5;
int const MAX_N = 10, MIN_N = 5;
int n;
int* data;
int** m;
int** s;
// init
void getData() {
    srand((unsigned)time(NULL));
    n = MIN_N + rand() % (MAX_N - MIN_N);
    //n = 5;
    data = new int[n+1]();
    //data[0]=30; data[1]=35;data[2]=15;data[3]=5;data[4]=10;data[5]=20;
    m = new int*[n+1];
    s = new int*[n+1];
    cout << "data: n = " << n << endl << "<";
    for (int i = 0; i < n+1; i++) {
        data[i] = MIN_DATA + rand() % (MAX_DATA - MIN_DATA);
        cout << data[i] << ", ";
        m[i] = new int[n+1]();
        s[i] = new int[n+1]();
    }
    cout << ">" << endl;
}
// 按照 r 来打印数据
void printR() {
    cout << endl << "  m[i,j] print : " << endl;
    for (int k = 1; k <= n; k++) {
        cout << "r=" << k;
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if ((j-i+1) == k) {
                    cout << "\tm[" << i << ", " << j << "]=" << m[i][j];
                }
            }
        }
        cout << endl;
    }
    cout << endl << "  s[i,j] print : " << endl;
    for (int k = 2; k <= n; k++) {
        cout << "r=" << k;
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if ((j-i+1) == k) {
                    cout << "\ts[" << i << ", " << j << "]=" << s[i][j];
                }
            }
        }
        cout << endl;
    }
}

// solve
void matrixChain(int* data,int n) {
    // init arr
    for (int i = 0; i < n+1; i++){ 
        for (int j = 0; j < n+1; j++) {
            s[i][j] = i;
        }
    }
    printR();
    for(int r = 2; r <= n; r++) { // chain of length [0 - n]  子问题划分 
        for(int i = 1; i <= (n-r+1); i++) { //  n-1+1 遍历其中的元素 
            int j = i + r -1; // j = 1 + 2 - 1 = 2 // 从子问题起始点 
            m[i][j] = m[i+1][j] + data[i-1]*data[i]*data[j];  // 计算当前数据 data[0]data[1]data[2] +m[2,2] = 优化值 m[1,2]
            s[i][j] = i; //s[i][j] = i;  标记元素 = 坐标 记录分割位置 s[1,2] = 1
            for(int k = i + 1; k <= j - 1; k++) { // 寻找其他划分 k = 2 < 2 - 1 
                int t = m[i][k] + m[k+1][j] + data[i-1]*data[k]*data[j]; // 前面的 + 后面的 + 相乘数据
                if (t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}
// solve
int recurMatrixChain(int* data,int i, int j) {
    if (i == j) { // 递归到最小单元 如 data[1][1] = 0; data[1][1]=1
        m[i][j] = 0;
        s[i][j] = i;
        return m[i][j]; 
    }
    m[i][j] = 1 << 30; // 该i到j 赋予最大值
    s[i][j] = i; // 分割点在i
    for (int k = i; k <= j-1; k++) { // 从i到j-1开始递归处理求最小值，在加上整体数据
        int q = recurMatrixChain(data, i, k) + recurMatrixChain(data, k+1, j) + data[i-1]*data[k]*data[j]; //data[0]*data[k]*data[j]
        if (q < m[i][j]) {
            m[i][j] = q;
            s[i][j] = k;
        }
    }
    return m[i][j];
}
// 打印过程
void printProcess(int start, int end) {
    if (start == end) return;
    printProcess(start, s[start][end]);
    printProcess(s[start][end]+1, end);
    cout << "(A" << start << "*A" <<end << ")";
    if (start != 1 || end !=n) {
        cout << "->";
    }
}
// 打印序列
void printOrder(int start, int end) {
    if (start == end) {
        cout << "A"<< end;
        return;
    }
    cout << "(";
    printOrder(start, s[start][end]);
    cout << " * ";
    printOrder(s[start][end]+1, end);
    cout << ")";
}
void printResult() {    
    cout << endl << "result : " << m[1][n] << endl;
    printOrder(1, n);
    cout << endl;
    printProcess(1, n);
}
int main() {
    getData();
    //matrixChain(data, n);
    recurMatrixChain(data, 1, n);
    printR();
    printResult();
    getchar();
    return 0;
}