网站设计有哪些语言版本,Wordpress连接ftp用户名,官方网站开发合同,免费做代理又不用进货1 动态规划 1.1 定义 动态规划的核心是状态和状态转移方程。 在记忆化搜索中#xff0c;可以为正在处理的表项声明一个引用#xff0c;简化对它的读写操作#xff1b; 动态规划解决的是多阶段决策问题#xff1b; 初始状态→│决策#xff11;│→│决策#xff12;│→…… 1 动态规划 1.1 定义 动态规划的核心是状态和状态转移方程。 在记忆化搜索中可以为正在处理的表项声明一个引用简化对它的读写操作 动态规划解决的是多阶段决策问题 初始状态→│决策│→│决策│→…→│决策│→结束状态 和分治法最大的区别在于适合于用动态规划的问题经过分解以后得到的子问题往往不是相互独立的即下一个子阶段的求解是建立在上一个子阶段的基础之上进行进一步的求解而不是相互独立的问题 动态规划问题一般由难到易分为一维动态规划二维动态规划多维动态规划以及多变量动态规划问题。其中多维动态规划问题又可以进行降维。动态规划问题求解的最重要的一步就是求解出 状态转移方程 1.2 特性 最优化原理如果问题的最优解所包含的子问题的解也是最优的就称该问题具有最优子结构即满足最优化原理.无后效性即某阶段状态一旦确定就不受这个状态以后决策的影响。也就是说某状态以后的过程不会影响以前的状态只与当前状态有关有重叠子问题即子问题之间是不独立的一个子问题在下一阶段决策中可能被多次使用到。该性质并不是动态规划适用的必要条件但是如果没有这条性质动态规划算法同其他算法相比就不具备优势动态规划可以避免多次计算1.3 例子 还是做题最实在! 1.3.1 最长公共子序列 问题描述给定两个序列X[1...m]和Y[1...n]求在两个序列中同时出现的最长子序列的长度。 如果按照最普通的方法就是遍历所有可能的情况将较短字符串中所有的子串和较长字符串中的子串进行比较取所有可能的情况中最长的子串 int DP::LongestCommonSubsequence(string X, string Y, int m, int n) {if (m 0 || n 0) {return 0;}if (X[m-1] Y[n-1]) {return LongestCommonSubsequence(X, Y, m-1, n-1) 1;}else {return max(LongestCommonSubsequence(X, Y, m-1, n), LongestCommonSubsequence(X, Y, m, n-1));}
}void DP::testLongestCommonSubstring() {string x abcdefg, y efg;int result LongestCommonSubsequence(x, y, (int)x.size(), (int)y.size());cout result: result;
}很显然这花费的时间是指数级的非常慢 那么采用动态规划是怎么做的 思路我们可以想象成树两个字符串都分别进行发散对于一个结点来说左边是左边的字符串进行改变右边则是右边的字符串进行改变直到两个字符串都相等。 第一步应该是找出递推公式 这里的 C[i,j] 代表的意思是字符串 X 中到达下标 i 和字符串 Y 中到达下标 j 的时候的最长子串个数 第二步是写出伪代码LCS(x,y,i,j)if x[i] y[j]then C[i,j] ← LCS(x,y,i-1,j-1)1else C[i,j] ← max{LCS(x,y,i-1,j),LCS(x,y,i,j-1)}return C[i,j] 最后是写出代码上面的伪代码对于每一种情况都会往前重新计算一遍完全没有必要用一个数组保存之前计算的值即可 int DP::LongestCommonSubsequence(string X, string Y, int m, int n) {vectorvectorint dp(X.size() 1, vectorint(Y.size() 1, 0));for (int i 1; i m; i) {for (int j 1; j n; j) {// 因为是从1开始的所以字符串下标要减去1if (X[i-1] Y[j-1]) {dp[i][j] dp[i-1][j-1] 1;}else {dp[i][j] max(dp[i-1][j], dp[i][j-1]);}}}return dp[m][n];
}void DP::testLongestCommonSubsequence() {string x abcdefg, y efg;int result LongestCommonSubsequence(x, y, (int)x.size(), (int)y.size());cout result: result;
}看看dp数组 0 0 0 0 0 00 1 1 1 1 10 1 2 2 2 20 1 2 3 3 30 1 2 3 3 30 1 2 3 3 30 1 2 3 4 40 1 2 3 4 5 参考文章动态规划Dynamic Programming 1.3.2 最长公共子串 和上面最长公共子序列不同的是子串要求连续不像子序列只要顺序保证是正确的就行了所以使用一个变量来记录 /*************************************** // 最长公共子串问题***************************************/
int DP::LongestCommonSubstring(string X, string Y, int m, int n) {vectorvectorint dp(X.size() 1, vectorint(Y.size() 1, 0));int max 0;for (int i 1; i m; i) {for (int j 1; j n; j) {// 因为是从1开始的所以字符串下标要减去1if (X[i-1] Y[j-1]) {if (dp[i-1][j-1]) {dp[i][j] dp[i-1][j-1] 1;}else {dp[i][j] 1;}if (dp[i][j] max) {max dp[i][j];}}}}for (int i 0; i m; i) {for (int j 0; j n; j) {cout dp[i][j];}cout endl;}return max;
}void DP::testLongestCommonSubstring() {string x abcdefg, y abcfg;int result LongestCommonSubstring(x, y, (int)x.size(), (int)y.size());cout result: result endl;
}看看dp数组 0 0 0 0 0 00 1 0 0 0 00 0 2 0 0 00 0 0 3 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 1 00 0 0 0 0 2 可以发现对角线上连续大于0的值则为长度最长的子串为abc长度为3次长为fg长度为2 1.3.3 最长递增子序列 问题描述给定一个序列X[1...m]求在这个序列中出现的最长递增子序列的长度。 /*************************************** // 最长递增子串问题***************************************/
int DP::LongestIncreasingSubstring(string X, int m) {vectorint dp(X.size(), 0);int max 0;for (int i 0; i m; i) { //到达dp[i] 1;for (int j 0; j i; j) {if (X[i] X[j]) {dp[i] dp[j] 1;}else { //因为是连续的所以只要不符合就重置dp[i] 1;}}}for (int i 0; i m; i) {cout dp[i];if (dp[i] max) {max dp[i];}}cout endl;return max;
}void DP::testLongestIncreasingSubstring() {string x babcak;int result LongestIncreasingSubstring(x, (int)x.size());cout result: result endl;
}1.3.4 矩阵链乘积 题目描述 给定n个矩阵A1,A2,…,An其中Ai与Ai1是可乘的i12…n-1。如何确定计算矩阵连乘积的计算次序使得依此次序计算矩阵连乘积需要的数乘次数最少。 思路 对于矩阵连乘问题最优解就是找到一种计算顺序使得计算次数最少 假设 dp[i, j] 表示第 i 个矩阵到达第 j 个矩阵这段的最优解 将矩阵连乘积 简记为A[i:j] 这里ij.假设这个最优解在第k处断开ikj则A[i:j]是最优的那么A[i,k]和A[k1:j]也是相应矩阵连乘的最优解。把i到j分成两部分看哪种分法乘的次数最少而k就是i到j中断开的部分也就是两个括号中间的部分 状态转移方程当ij时A[i,j]Ai, m[i,j]0;(表示只有一个矩阵,如A1,没有和其他矩阵相乘,故乘的次数为0)当ij时m[i,j]min{m[i,k]m[k1,j] pi-1*pk*pj} ,其中 ikj也就是 实现 /*************************************** // 矩阵链乘积求最小乘积次数***************************************/
void DP::MatrixChainMultiplication(vectorint data, int n,vectorvectorint m_dp, vectorvectorint s_dp) {//矩阵段长度为1,则 dp[][] 中对角线的值为0,表示只有一个矩阵,没有相乘的.for(int i 1;in;i)m_dp[i][i] 0;// 从第二个开始第一个也是0当前的乘次数取决于下一个的乘次数// 对角线循环r表示矩阵的长度(2,3…逐渐变长)for(int r 2;rn;r) {// 行循环for(int i 1; in-r1; i) {// 列的控制当前矩阵段(Ai~Aj)的起始为Ai,尾为Ajint j ri-1;//例如对(A2~A4),则i2,j4,下面一行的m[2][4] m[3][4]p[1]*p[2]*p[4],即A2(A3A4)m_dp[i][j] m_dp[i1][j] data[i-1]*data[i]*data[j]; //计算次数s_dp[i][j] i;//记录断开点的索引//循环求出(Ai~Aj)中的最小数乘次数遍历所有可能的情况for(int k i1 ; kj;k) {//将矩阵段(Ai~Aj)分成左右2部分(左m[i][k],右m[k1][j])//再加上左右2部分最后相乘的次数(p[i-1] *p[k]*p[j])int t m_dp[i][k] m_dp[k1][j] data[i-1] *data[k]*data[j];if(t m_dp[i][j]) {m_dp[i][j] t;s_dp[i][j] k; //保存最小的,即最优的结果}}}}
}void DP::testMatrixChainMultiplication() {vectorint data {30,35,15,5,10,20,25};//记录6个矩阵的行和列注意相邻矩阵的行和列是相同的vectorvectorint m_dp(7, vectorint(7, 0));//存储第i个矩阵到第j个矩阵的计算代价以乘法次数来表示vectorvectorint s_dp(7, vectorint(7, 0));//存储第i个矩阵到第j个矩阵的最小代价时的分为两部分的位置int n6;//矩阵个数MatrixChainMultiplication(data, n , m_dp, s_dp);cout ---计算代价--- endl;for (int i 0; i m_dp.size(); i) {for (int j 0; j m_dp[0].size(); j) {cout m_dp[i][j];}cout endl;}cout ---最小代价时分为两边的位置 endl;for (int i 0; i s_dp.size(); i) {for (int j 0; j s_dp[0].size(); j) {cout s_dp[i][j];}cout endl;}
}运行结果为 ---计算代价---0 0 0 0 0 0 00 0 15750 7875 9375 11875 151250 0 0 2625 4375 7125 105000 0 0 0 750 2500 53750 0 0 0 0 1000 35000 0 0 0 0 0 50000 0 0 0 0 0 0
---最小代价时分为两边的位置0 0 0 0 0 0 00 0 1 1 3 3 30 0 0 2 3 3 30 0 0 0 3 3 30 0 0 0 0 4 50 0 0 0 0 0 50 0 0 0 0 0 0 表示第i个矩阵到第j个矩阵的计算代价矩阵m[i][j]和表示第i个矩阵到第j个矩阵的最小代价时的分为两部分的位置矩阵s[i][j]的结果如下图 从上面左图的m矩阵可以看出任意第i个到第j个矩阵连乘的乘法次数。最终的加括号形式为A1(A2A3))((A4A5)A6) 参考文章【算法导论】 动态规划之矩阵链乘法0010算法笔记——【动态规划】矩阵连乘问题 1.3.5 数塔问题 问题描述 数塔第i层有i个结点要求从顶层走到底层若每一步只能走到相邻的结点则经过的结点的数字之和最大是多少 用二维数组则为 9
12 15
10 6 8
2 18 9 5
19 7 10 4 16假设9首先被输入是第 0 层越往下层数不断递增 思路 为了保证整条路径的和是最大的下一层的走向取决于再下一层上的最大值是否已经求出才能决定所以要做一个自顶向下的分析自底向上的计算 状态转移方程dp[i][j] max(dp[i1][j], dp[i1][j1]) data[i][j]dp[i1][j] 为左结点dp[i1][j1] 为右结点 实现 /*************************************** // 数塔问题***************************************/
int DP::MaxSumTower(vectorvectorint nums, int m, int n) {vectorvectorint dp(m, vectorint(n, 0));// 用底层的值来初始化dpm为行n为列for (int i 0; i n; i) {dp[m-1][i] nums[m-1][i];}// 自底向上父结点的最大值取决于左结点或者右结点的最大值for (int i m-2; i 0; i--) {for (int j 0; j n; j) {if (i j) { //过滤多余的dp[i][j] std::max(dp[i1][j], dp[i1][j1]) nums[i][j];}}}for (int i 0; i m; i) {for (int j 0; j n; j) {cout dp[i][j];}cout endl;}return dp[0][0];
}1.3.6 01背包问题 题目描述 有编号分别为a,b,c,d,e的五件物品它们的重量分别是2,2,6,5,4它们的价值分别是6,3,5,4,6现在给你个承重为10的背包如何让背包里装入的物品具有最大的价值总和 思路 dp[x][y] 表示体积不超过 y 且可选前 x 种物品的情况下的最大总价值 递归关系 mp[0][y] 0mp[x][0] 0当 v[x] y 时mp[x][y] mp[x-1][y]当 v[x] y 时mp[x][y] max{ mp[x-1][y], p[x] mp[x-1][y-v[x]] }解释如下 表示体积不超过 y 且可选前 0 种物品的情况下的最大总价值没有物品可选所以总价值为 0表示体积不超过 0 且可选前 x 种物品的情况下的最大总价值没有物品可选所以总价值为 0因为 x 这件物品的体积已经超过所能允许的最大体积了所以肯定不能放这件物品 那么只能在前 x-1 件物品里选了x 这件物品可能放入背包也可能不放入背包所以取前两者的最大值就好了 这样就将前两种情况都包括进来了实现 /*************************************** // 01背包问题***************************************/
int DP::ZeroOneBackpack(vectorGoods goods, int limit_weight) {int m goods.size();int n limit_weight;vectorvectorint dp(m 1, vectorint(n 1, 0));// 没有选择物品的时候价值为0for (int i 1; i n; i) {dp[0][i] 0;}// 重量为0的时候什么物品都选不了价值自然也为0for (int i 1; i m; i) {dp[i][0] 0;}for (int i 1; i m; i) {for (int j 1; j n; j) {if (goods[i-1].weight j) { //超出限制的重量dp[i][j] dp[i-1][j];}else { //可能放入背包也可能不放入背包取两者情况的最大值dp[i][j] std::max(dp[i-1][j], dp[i-1][j - goods[i-1].weight] goods[i-1].value);}}}for (int i 0; i m; i) {for (int j 0; j n; j) {cout dp[i][j];}cout endl;}return dp[m][n];
}void DP::testZeroOneBackpack() {vectorGoods goods;goods.emplace_back(0, 0);goods.emplace_back(60, 10);goods.emplace_back(100, 20);goods.emplace_back(120, 30);int result ZeroOneBackpack(goods, 50);cout result: result endl;
}1.3.7 最大连续子序列之和 问题描述给定一个序列X[1...m]求在这个序列中出现的最大的连续子序列之和。 状态转移方程dp[i] std::max(dp[i-1] nums[i], nums[i]); 实现/*************************************** // 最大连续子序列和***************************************/
int DP::MaxContinusSubsequenceSum(int* nums, int m) {vectorint dp(m, 0);int max INT_MIN;dp[0] nums[0];for (int j 1; j m; j) {dp[j] std::max(dp[j-1] nums[j], nums[j]);}for (int i 0; i m; i) {cout dp[i];if (dp[i] max) {max dp[i];}}cout endl;return max;
}void DP::testMaxContinusSubsequenceSum() {int data[] {1,-2,3,-1,7};int result MaxContinusSubsequenceSum(data, 5);cout result: result endl;
}转载于:https://www.cnblogs.com/George1994/p/6710675.html
