一、基本思想
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,并将子问题的求解结果存储起来避免重复求解,从而一步步获取最优解的处理算法。
动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 )
动态规划的特性主要包括:
- 分解原问题:动态规划将原问题分解为若干个相似的子问题,这些子问题之间相互独立,并且每个子问题只需要解决一次。
- 储存子问题的解:动态规划会储存子问题的解,以避免重复计算,这是动态规划能够高效解决复杂问题的关键。
- 状态转移方程:动态规划的本质在于对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。
- 无后效性:每个状态都是“过去历史的一个完整总结”,也就是说,每个状态都包含了它过去的历史信息,而不会受到未来状态的影响。
- 阶段性和相互联系性:动态规划通常将问题划分为若干个阶段,每个阶段都对应着一组状态,这些状态之间相互联系,构成了整个问题的状态转移过程。
- 决策变量和允许决策集合:在动态规划中,每个阶段都包含若干个决策变量,这些决策变量的取值范围称为允许决策集合。
- 状态变量和状态集合:描述各阶段状态的变量称为状态变量,常用sk表示第k阶段的状态变量,状态变量sk的取值集合称为状态集合,用Sk表示。
二、案例说明——背包问题
动态规划可以通过填表的方式来逐步推进,得到最优解。在填表法中,会为每个子问题预先计算出最优解并填入表中,然后通过查表来获取原问题的最优解。
背包问题:有一个背包,容量为4磅 , 现有如下物品
物品 | 重量 | 价格 |
---|---|---|
吉他(G) | 1 | 1500 |
音响(S) | 4 | 3000 |
电脑(L) | 3 | 2000 |
- 要求达到的目标为装入的背包的总价值最大,并且重量不超出
- 要求装入的物品不能重复
背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是:每种物品都有无限件可用)
这里的问题属于01背包,即每个物品最多放一个。而无限背包可以转化为01背包。
思路: 利用动态规划来解决。
假设背包容量为weight
,有 n
个物品,每个物品的重量为 w[i]
,价值为 v[i]
。
- 设
dp[i][j]
表示前 `i` 个 物品,容量为j
时的最大价值。 —— 定义动态规划的状态,通常是数组或集合。 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
,表示在第i
个物品和不放第i
个物品中选取一个最优解。 —— 定义状态转移方程,根据问题最优解的定义,确定状态之间的转移关系。dp[0][j] = 0
,表示不选择任何物品时的价值为0。—— 确定最基本的子问题的解作为边界条件。- 填表,从第一个物品开始填表直到最后一个物品。—— 每个子问题的最优解填入对应的状态位置。
- 查询最优解,
dp[n][weight]
即前n个物品,容量为w时的最大价值。 —— 根据需求解的问题的目标状态去查询对应子问题的最优解。
public staic int knapsack(int[] w, int[] v, int weight) {int n = w.length;int[][] dp = new int[n + 1][weigth + 1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= weigth; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else if (j < w[i - 1]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);}}}return dp[n][weight];
}