[最优化方法]动态规划 - 矩阵链乘法乘积问题
详细请看算法导论教程
// MatrixChainOrder.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdlib.h>
#include "stdio.h"
void MatrixChainOrder(int*p, int n);
void printMatrixChainOrder(int** s_mat, int start_p, int end_p);
int _tmain(int argc, _TCHAR* argv[])
{
//算法导论数的参数
int p[7] = { 30, 35, 15, 5, 10, 20, 25 };
//代入求解
MatrixChainOrder(p, 7);
system("Pause");
return 0;
}
void MatrixChainOrder(int*p, int n)
{
int len = n - 1;
int mul_len, i, j, k,cost;
int **m_mat = (int **)malloc(n * sizeof(int *));
int **s_mat = (int **)malloc(n * sizeof(int *));
for (i = 0; i < n; i++)
{
m_mat[i] = (int *)malloc(n * sizeof(int));
s_mat[i] = (int *)malloc(n * sizeof(int));
}
//初始化m矩阵
for (i = 1; i <= len; i++)
{
m_mat[i][i] = 0;
}
//主循环
for (mul_len = 2; mul_len <= len; mul_len++)
{
for (i = 1; i <= len - mul_len + 1; i++)
{
j = i + mul_len - 1;
m_mat[i][j] = 100000000;//足够大即可
for (k = i; k < j; k++)
{
cost = m_mat[i][k] + m_mat[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost <= m_mat[i][j])
{
m_mat[i][j] = cost;
s_mat[i][j] = k;
}
}
}
}
//打印观察矩阵
/*
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
printf("%d ", m_mat[i][j]);
}
printf("\n");
}*/
//打印矩阵解
printMatrixChainOrder(s_mat, 1, len);
return;
}
void printMatrixChainOrder(int** s_mat, int start_p, int end_p)
{
if (start_p == end_p)
printf("A%d", start_p);
else
{
printf("(");
printMatrixChainOrder(s_mat, start_p, s_mat[start_p][end_p]);
printMatrixChainOrder(s_mat, s_mat[start_p][end_p]+1, end_p);
printf(")");
}
return;
}