射洪网站建设工作室,做神马网站快速排名,工程人才招聘网,网站建设培训教程 新手入门到精通动态规划详解
动态规划 (Dynamic Programming) 是一种算法思想#xff0c;用于解决一些复杂的问题。本文将介绍动态规划的分类、概念和经典例题讲解。
动态规划的分类
动态规划可以分为以下两种类型#xff1a;
0/1背包问题#xff1a;该问题是动态规划的一种基本类型。…动态规划详解
动态规划 (Dynamic Programming) 是一种算法思想用于解决一些复杂的问题。本文将介绍动态规划的分类、概念和经典例题讲解。
动态规划的分类
动态规划可以分为以下两种类型
0/1背包问题该问题是动态规划的一种基本类型。在背包问题中有n个物品可以放入容量为W的背包中每个物品有自己的重量和价值。需要选择哪些物品能够最大化背包的总价值。最长公共子序列问题该问题是另一种经典的动态规划类型涉及到两个字符串并找到这两个字符串之间的最长公共子序列。
动态规划的概念
在解决动态规划问题时我们需要定义以下概念
状态 (State)问题中需要优化的变量如背包问题中的容量最长公共子序列问题中的字符串长度等。状态转移方程 (State Transition Equation)描述状态之间的转移过程即问题的递推关系。例如在背包问题中每个物品可以放入背包或不放入背包。因此状态转移方程可以表示为 d p [ i ] [ j ] max ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w i ] v i ) dp[i][j] \max(dp[i-1][j], dp[i-1][j-w_i]v_i) dp[i][j]max(dp[i−1][j],dp[i−1][j−wi]vi) 其中dp[i][j]表示在使用前i个物品时填满j容量的背包的最大价值。初始状态 (Initial State)问题的初始条件通常为问题规模最小的情况下的答案。在背包问题中初始状态为dp[0][0]0。边界状态 (Boundary State)问题的边界条件在状态转移过程中需要特别处理的状态。在背包问题中背包的容量不能为负数因此需要在状态转移方程中特别处理。
经典例题讲解
下面我们将分别介绍0/1背包问题和最长公共子序列问题的解法。
1. 0/1背包问题
题目描述有n个物品和一个容量为W的背包。第i个物品的重量为wi价值为vi。现在需要选择一些物品放入背包使得放入的物品的总重量不超过W且总价值最大。求最大价值。
解题思路定义状态dp[i][j]为在使用前i个物品时填满j容量的背包的最大价值。状态转移方程如下所示 d p [ i ] [ j ] { d p [ i − 1 ] [ j ] , j w i max ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w i ] v i ) , j ≥ w i dp[i][j] \begin{cases}dp[i-1][j],jw_i\\ \max(dp[i-1][j], dp[i-1][j-w_i]v_i),j\ge w_i\end{cases} dp[i][j]{dp[i−1][j],max(dp[i−1][j],dp[i−1][j−wi]vi),jwij≥wi 其中dp[i-1][j]表示不放入第i个物品的最大价值dp[i-1][j-w[i]]v[i]表示将第i个物品加入背包的最大价值。需要注意的是如果当前背包容量小于物品的重量就不能将该物品放入背包。因此需要特别处理背包容量小于物品重量的情况。
代码实现
int dp[101][1001];
int weight[101], value[101];int knapSack(int n, int w)
{memset(dp, 0, sizeof(dp));for (int i 1; i n; i) {for (int j 1; j w; j) {if (j weight[i]) {dp[i][j] dp[i-1][j];} else {dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]]value[i]);}}}return dp[n][w];
}2. 最长公共子序列问题
题目描述给定两个字符串A和B找到它们的最长公共子序列 (LCS)。
解题思路定义状态dp[i][j]为字符串A的前i个字符和字符串B的前j个字符的LCS长度。状态转移方程如下所示 d p [ i ] [ j ] { 0 , i 0 或 j 0 d p [ i − 1 ] [ j − 1 ] 1 , A i B j max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) , A i ≠ B j dp[i][j] \begin{cases}0,i0\text{或}j0\\ dp[i-1][j-1]1,A_iB_j\\ \max(dp[i-1][j], dp[i][j-1]),A_i\neq B_j\end{cases} dp[i][j]⎩ ⎨ ⎧0,dp[i−1][j−1]1,max(dp[i−1][j],dp[i][j−1]),i0或j0AiBjAiBj
当A[i-1]等于B[j-1]时dp[i][j]等于dp[i-1][j-1]1表示A和B中的相同字符加上它们前面的LCS。当它们不相等时LCS为它们前面的LCS的最大值即dp[i-1][j]和dp[i][j-1]的最大值。
代码实现
int dp[1001][1001];
string A, B;int LCS(int n, int m)
{for (int i 0; i n; i) {for (int j 0; j m; j) {if (i 0 || j 0) {dp[i][j] 0;} else if (A[i-1] B[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[n][m];
}结语
动态规划是一种非常重要的算法思想它通常用于解决复杂的问题。在应用动态规划解决问题时需要注意定义状态、状态转移方程、初始状态和边界状态等概念。对于不同类型的动态规划问题需要采用不同的解决方法。希望本文能够帮助读者加深对动态规划的理解。
