算法简析"/>
C++动态规划算法简析
动态规划
动态规划主要用于求全局最优解,通常可以解决以下问题:
- 优化问题:例如最短路径问题、背包问题、调度问题等,这些问题通常具有子问题重叠的特点,因此可以通过动态规划的方式避免重复计算,从而提高算法的效率。
- 求最大值或最小值问题:例如最长上升子序列、最大连续子数组和等,这些问题通常可以通过建立一个状态转移方程来逐步求解最终结果。
- 求方案数问题:例如路径计数问题、背包问题、组合问题等,这些问题通常可以通过建立一个状态转移方程来逐步求解方案数。
- 求最优方案问题:例如字符串编辑距离、图像识别、语音识别等,这些问题通常可以通过建立一个状态转移方程来逐步求解最优方案。
解题思路
动态规划运用分治的思想,将大问题拆解成许多小问题。
比如01背包问题,首先求只装入一个物品时的最大价值,再此基础再求装入两个物品,最终求得计入所有物品时的最大价值。
再比如Floyd算法,首先求解只能经过一个结点的情况,再此基础上,再计算经过两个节点的情况,以此类推,最终找到多源最短路解。
解题步骤如下:
- 定义变量和状态
- 找到约束条件
- 确认求值属性(基于问题求最大值、最小值或者其他)
- 列出状态转移方程
具体例子
01背包问题
给定一个重量数组v和价值数组w,以及一个背包的最大承重量m,每个物品只能用一次,求在不超过背包最大承重量的前提下,能够装入背包的物品的最大总价值。v=[1,2,3,4] w=[3,2,4,5]。
- 首先确定变量。i: 当前最多装入物品数(比如1当前背包只能装一个物品),j :当前背包已使用容量(比如4代表背包现在已经用了4个体积)
- 找到约束条件。每个物品只能用一次、不超过背包最大承重量
- 确认求值属性。求装入背包的最大总价值
- 列出状态转移方程。f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i])
for(int i = 1; i <= n; ++i) // 选取多少个物品for(int j = 0; j <= m; j++){ // 容积f[i][j] = f[i-1][j];if(j > v[i]) // 如果总容积大于当前物品重量f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]); // 找到在没选择该物品前的最大价值}
更多推荐
C++动态规划算法简析
发布评论