python编程网站,网站布局设计规则,临沂公司做网站,wordpress网站小屏基本要素#xff1a; #xff08;1#xff09;最优子结构性质 #xff08;2#xff09;重叠子问题性质 思想#xff1a; 动态规划和分治法类似#xff0c;其基本思想也是将待求解问题分解成若干个子问题#xff0c;先求解子问题#xff0c;然后从这些子问题的解得到原…基本要素 1最优子结构性质 2重叠子问题性质 思想 动态规划和分治法类似其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。 与分治法不同的是动态规划法中分解得到的子问题不是互相独立的。若用分治法来解这类子问题分解得到的子问题数目非常多最后解决原问题需要耗费指数时间。但是这些子问题有很多是相同的也就是同一个子问题被计算了很多次不同子问题的数量可能只有多项式量级。 如果我们保存已经解决的子问题的解需要解相同子问题时找出已经计算出的解这样可以减少大量重复计算最终得到多项式时间算法。 经常用一个表来记录所有已解决的子问题的解。不管该子问题以后是否被利用只要它被计算过就将其结果填入表中。这就是动态规划的基本思想。具体的动态规划算法多种多样但它们具有相同的填表格式。 —计算机算法设计与分析 第四版 王晓东— ####动态规划例子矩阵连乘问题 给定N个矩阵{A1,A2,A3,An}其中Ai与A(i1)是可以相乘的考察这N个矩阵的连乘积A1A2,An。 由于矩阵乘法满足结合律故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定比如下面4个矩阵的连乘积。 A1A2 A3 A4 1,(2,(3,4)) 1,((2,3),4) (1,2),(3,4) (1,(2,3)),4 ((1,2),3),4
#####最优解的结构 计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k1:n]的次序也是最优的。 A[1:n] A[1:k] * A[K1:n] 其中 ( 1 k n) 递推关系如下 m(i , j) 0 ,(ij) m(i , j) min{ m(i,k) m(k1,j) P(i-1)P(k)P(j) } ,(i j ) #####重叠子问题 重叠的子问题主要体现在m表格里
例题我们计算如下6个矩阵的连乘积 A1 ------ A2 ------ A3 ----- A4 ----- A5 ----- A6 (3035) (3515) (155) (510) (1020) (2025)
const int N 6;
int table[N 1][N 1];
int p[N 1] { 30, 35, 15, 5, 10, 20, 25 };
void MatrixMulti()
{for (int r 2; r N; r) //r表示连乘矩阵的个数{for (int i 1; i N - r 1; i) //i表示起始矩阵索引{int j i r - 1; //j表示终止矩阵索引for (int k i; k j; k){int temp table[i][k] table[k1][j] p[i - 1] * p[k] * p[j];table[i][j] (table[i][j] 0) ? temp : min(table[i][j], temp);}}}
}
int main()
{MatrixMulti();cout 最小乘积为 table[1][N] endl;return 0;
}
/*输出结果
最小乘积为15125
table数组内容为
0 0 0 0 0 0 0
0 0 15750 7875 9375 11875 15125
0 0 0 2625 4375 7125 10500
0 0 0 0 750 2500 5375
0 0 0 0 0 1000 3500
0 0 0 0 0 0 5000
0 0 0 0 0 0 0*/
