动态规划:矩阵连乘问题
规划 动态 矩阵 问题
2023-09-11 14:20:59 时间
下面仅仅是对此问题的一个代码实现,详细理论部分请參见王晓东《算法设计与分析》第2版3.1节 矩阵连乘问题。
#include <iostream> #include <iomanip> using namespace std; #define MAX_COUNT 20 //矩阵属性 struct tagMatrixAttribute { int row; int col; }; //矩阵连乘加括号求解 void MatrixChain( tagMatrixAttribute mMatrix[], int nCount, int m[][MAX_COUNT], int s[][MAX_COUNT] ) { for ( int i = 0; i < nCount; ++i ) m[i][i] = 0; for ( int r = 1; r < nCount; ++r ) { for ( int i = 0; i < nCount - r; ++i ) { int j = i + r; //从k处断开,i <= k < j int k = i; m[i][j] = m[i][k] + m[k+1][j] + mMatrix[i].row * mMatrix[k].col * mMatrix[j].col; s[i][j] = k; int nTemp = 0; for( k = i + 1; k < j; ++k ) { nTemp = m[i][k] + m[k+1][j] + mMatrix[i].row * mMatrix[k].col * mMatrix[j].col; if ( nTemp < m[i][j] ) { m[i][j] = nTemp; s[i][j] = k; } } } } } //构造结果 void TraceBack( int s[][MAX_COUNT], int i, int j ) { if ( i == j ) { cout << "A" << i+1; return; } cout << "("; TraceBack( s, i, s[i][j] ); TraceBack( s, s[i][j]+1, j ); cout << ")"; } void PrintArray( int nArray[][MAX_COUNT], int nCount ) { cout << left; for( int i = 0; i < nCount; ++i ) { for ( int j = 0; j < nCount; ++j ) { cout << setw(7) << nArray[i][j] << " "; } cout << endl; } cout << right; } int main() { tagMatrixAttribute mMatrixAttrArray[] = { 30, 35, 35, 15, 15, 5, 5, 10, 10, 20, 20, 25 }; // tagMatrixAttribute mMatrixAttrArray[] = { // 10, 100, // 100, 5, // 5, 50 // }; int nCount = _countof( mMatrixAttrArray ); int m[MAX_COUNT][MAX_COUNT]; int s[MAX_COUNT][MAX_COUNT]; memset( m, 0, sizeof(m) ); memset( s, 0, sizeof(s) ); MatrixChain( mMatrixAttrArray, nCount, m, s ); PrintArray( m, nCount ); cout << endl; PrintArray( s, nCount ); cout << endl; //构造结果 TraceBack( s, 0, nCount-1 ); cout << endl; return 0; }
作者:山丘儿
转载请标明出处。谢谢。
原文地址:http://blog.csdn.net/s634772208/article/details/46683087
相关文章
- 怎么样才能在手机上设置时间规划进行自律?
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java实现 LeetCode 343 整数拆分(动态规划入门经典)
- Java动态规划实现最短路径问题
- (动态规划)最长回文子序列、回文子序列个数
- Leetcode学习计划之动态规划入门day18(300,376)
- Leetcode学习计划之动态规划入门day7(1014,121,122)
- Leetcode学习计划之动态规划入门day3(198,213,740)
- Leetcode717: 1比特与2比特字符(simple, 动态规划)
- 【【henuacm2016级暑期训练】动态规划专题 L】Civilization
- 【codeforces 761C】Dasha and Password(动态规划做法)
- 基于Dijkstra和A*算法的机器人路径规划(Matlab代码实现)
- 基于蚁群算法的时延Petri网(ACOTPN)路径规划算法(Matlab代码实现)
- 【混合遗传规划和正交最小二乘法】基于混合遗传规划和正交最小二乘法的线性参数动态输入输出系统的模型结构识别(Matlab代码实现)
- 18篇文章系统解读:中台规划如何撬动企业IT基础设施转型升级
- 野生前端的数据结构练习(11)动态规划算法
- 790. 多米诺和托米诺平铺-动态规划算法优化
- 714. 买卖股票的最佳时机含手续费-动态规划算法
- 915. 分割数组-动态规划算法
- 《数字中国建设整体布局规划》充分发挥“数据”生产要素:形成横向打通、纵向贯通、协调有力的一体化推进格局...
- [LeetCode] 64. 最小路径和 ☆☆☆(动态规划)
- 动态规划-hdoj-4832-百度之星2014初赛第二场
- Android 根据规划 Touch 分配和消费机制的事件
- [LeetCode] Network Delay Time 网络延迟时间——最短路算法 Bellman-Ford(DP) 和 dijkstra(本质上就是BFS的迭代变种) 动态规划,要会模板!
- 【IEEE2014】EET:基于采样的机器人运动规划中的平衡勘探与开发
- 中小型局域网规划实战案例