Algorithm_《算法导论》乘法链问题

发表于 | 分类于 |

乘法链问题算是比较好理解的了，晚上写了半个小时就调出来了，作为动态规划的第二篇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Matrix.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

/**
矩阵的乘法链问题：多个矩阵相乘时，怎么加括号，总的乘法次数最小
比如3个矩阵相乘，可以先计算前两个的积，再乘以第三个，也可以先计算后两个的积
再乘以第一个。两种方法的乘法次数不同。
来源：《算法导论》第四版中文版P205
分类：动态规划，算法，ACM
@Author:XiaJun
@Time:May 5th,2018
**/

int main()
{
	//6个矩阵，行数和列数
	int mat[6][2] = {{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}};

	//一个5行5列的矩阵，记录最优子结构的值
	int child[6][6];
	int i,j,dis,k = 0,min;
	//初始化该矩阵
	for(i = 0;i < 6;i++) {
		for(j = 0;j < 6;j++) {
			child[i][j] = 0;
		}
	}

	//两个矩阵相乘的最优子结构的值是已知的
	for(i = 0;i < 5;i++) {
		child[i][i+1] = mat[i][0]*mat[i][1]*mat[i+1][1];
	}

	//计算所有的最优子结构
	for(dis = 2;dis < 6;dis++) {
		for(i = 0;dis+i < 6;i++) {//i：最优子结构的起始处
			j = i+dis;//j：最优子结构的结束处
			min = mat[i][0]*mat[i][1]*mat[j][1]+mat[i+1][j];
			for(k = i;k < j;k++) {
				int cur = mat[i][0]*mat[k][1]*mat[j][1]+child[i][k]+child[k+1][j];
				min = min > cur?cur:min;
			}
			child[i][j] = min;
		}
	}

	printf("最少的乘法计算次数是：%d",child[0][5]);

	return 0;
}