《动态规划解决背包问题》课件

动态规划解决背包问题什么是背包问题定义核心背包问题是一类经典的组合优化问题，它描述了在给定容量的背包中，选择物品以最大化价值的问题它是一种典型的资源分配问题，在经济学、计算机科学、运筹学等领域都有着广泛的应用背包问题的应用场景货车装载根据货车容量和货物价值，选择装载哪些货物以获得最大1利润投资组合优化在有限的资金预算下，选择哪些股票或债券以最大化2投资回报项目管理根据项目预算和资源，选择哪些项目进行投资以获得最大的经济效益背包问题的分类背包问题完全背包问题多重背包问题0-1每个物品只能选择一次，要么放入背每个物品可以无限次地选择，可以多每个物品有固定的数量，可以选择多包，要么不放入背包次放入背包个，但不能超过其数量限制背包问题0-1背包问题是最基本的一种背包问题它假设每个物品只能选择一次，也0-1就是说，对于每个物品，我们只有两种选择要么放入背包，要么不放入背包背包问题的描述0-1问题描述举例给定一个容量为的背包和个物品，每个物品有重量例如，假设我们有一个容量为的背包，有个物品物品W ni wi103和价值目标是选择一些物品放入背包，使得背包中物品的的重量为，价值为；物品的重量为，价值为；vi1262310总价值最大，同时不超过背包的容量物品的重量为，价值为我们的目标是选择物品放入3412背包，使背包中物品的总价值最大背包问题的动态规划求解0-1定义状态1表示从前个物品中选择物品放入容量为的背dp[i][j]i j包，所能得到的最大价值状态转移方程2dp[i][j]=maxdp[i-1][j],dp[i-1][j-wi]+vi边界条件3dp

[0][j]=0,dp[i]

[0]=0动态规划的核心思想最优子结构问题的最优解包含子问题的最优解例如，背包问题的最优解包含了从前个物品中选择物品放入容量为的背包的最i-1j优解无后效性子问题的求解不会影响其他子问题的求解例如，选择物品i放入背包不会影响前个物品的选择i-1背包问题的状态定义0-1状态意义状态定义代表了在考虑前个物品时，容量为的背包所能装载dp[i][j]i j表示从前个物品中选择物品放入容量为的背包，所的最大价值dp[i][j]i j能得到的最大价值背包问题的状态转移方程0-1dp[i][j]=maxdp[i-1][j],dp[i-1][j-wi]+vi表示从前个物品中选择物品放入容量为的背包，所能得到的最大价值1i jdp[i-1][j]2表示不选择第个物品，从前个物品中选择物品放入容量为的背i i-1j包，所能得到的最大价值dp[i-1][j-wi]+vi3表示选择第个物品，从前个物品中选择物品放入容量i i-1为的背包，所能得到的最大价值，再加上第个物品的j-wi i价值背包问题的优化0-1空间优化时间优化由于只依赖于和可以使用二进制枚举、贪心算法等方法进行dp[i][j]dp[i-1][j]12，因此可以使用滚动数组进时间优化，但这些方法不一定能得到最优dp[i-1][j-wi]行空间优化，将二维数组压缩为一维数组解完全背包问题完全背包问题是背包问题的一种变体它假设每个物品可以无限次地选择，也就是说，对于每个物品，我们可以选择任意多次，只要不超过背包的容量完全背包问题的描述问题描述举例给定一个容量为的背包和个物品，每个物品有重量例如，假设我们有一个容量为的背包，有个物品物品W ni wi103和价值目标是选择一些物品放入背包，使得背包中物品的的重量为，价值为；物品的重量为，价值为；vi1262310总价值最大，同时不超过背包的容量，每个物品可以选择任意多物品的重量为，价值为我们的目标是选择物品放入3412次背包，使背包中物品的总价值最大，每个物品可以选择任意多次完全背包问题的动态规划求解定义状态1表示从前个物品中选择物品放入容量为的背dp[i][j]i j包，所能得到的最大价值状态转移方程2dp[i][j]=maxdp[i-1][j],dp[i][j-wi]+vi边界条件3dp

[0][j]=0,dp[i]

[0]=0完全背包问题的状态定义状态定义表示从前个物品中选择物品放入容量为的背包，所能得到dp[i][j]i j的最大价值状态意义代表了在考虑前个物品时，容量为的背包所能装载的dp[i][j]i j最大价值，每个物品可以被选择多次完全背包问题的状态转移方程dp[i][j]=maxdp[i-1][j],dp[i][j-wi]+vi表示从前个物品中选择物品放入容量为的背包，所能得到的最大价值1i jdp[i-1][j]2表示不选择第个物品，从前个物品中选择物品放入容量为的背i i-1j包，所能得到的最大价值dp[i][j-wi]+vi3表示选择第个物品，从前个物品中选择物品放入容量为i i的背包，所能得到的最大价值，再加上第个物品的价j-wi i值完全背包问题的优化空间优化时间优化与背包问题类似，可以使用滚动0-112可以使用单调队列进行时间优化，将时数组进行空间优化，将二维数组压缩为间复杂度降低到OnW一维数组多重背包问题多重背包问题是背包问题的一种变体它假设每个物品有固定的数量，可以选择多个，但不能超过其数量限制多重背包问题的描述问题描述举例给定一个容量为的背包和个物品，每个物品有重量例如，假设我们有一个容量为的背包，有个物品物品W ni wi103和价值以及数量目标是选择一些物品放入背包，使得背的重量为，价值为，数量为；物品的重量为，vi ci126323包中物品的总价值最大，同时不超过背包的容量，每个物品可以价值为，数量为；物品的重量为，价值为，数1023412选择多个，但不能超过其数量限制量为我们的目标是选择物品放入背包，使背包中物品的总1价值最大，每个物品可以选择多个，但不能超过其数量限制多重背包问题的动态规划求解定义状态1表示从前个物品中选择物品放入容量为的背dp[i][j]i j包，所能得到的最大价值状态转移方程2dp[i][j]=maxdp[i-1][j],dp[i-1][j-k*wi]+k*vi边界条件3dp

[0][j]=0,dp[i]

[0]=0多重背包问题的状态定义状态定义表示从前个物品中选择物品放入容量为的背包，所能得到dp[i][j]i j的最大价值状态意义代表了在考虑前个物品时，容量为的背包所能装载的dp[i][j]i j最大价值，每个物品可以被选择多次，但不能超过其数量限制多重背包问题的状态转移方程dp[i][j]=maxdp[i-1][j],dp[i-1][j-k*wi]+k*vi表示从前个物品中选择物品放入容量为的背包，所能得到的最大价值1i jdp[i-1][j]2表示不选择第个物品，从前个物品中选择物品放入容量为的背i i-1j包，所能得到的最大价值dp[i-1][j-k*wi]+k*vi表示选择第个物品，从前个物品中选择物品放入容量为i i-13的背包，所能得到的最大价值，再加上选择个第个j-k*wi k i物品的价值多重背包问题的优化二进制分组单调队列将每个物品的数量分成、、、、（其中ci

1248...2^k2^k）、这样多个物品，将多重背包问题转化为类似完全背包问题，可以使用单调队列进行时间优化，将时间复=ci ci-2^k0-1背包问题杂度降低到OnW12背包问题的拓展应用股票交易的最大收益最长公共子序列股票交易的最大收益股票交易的最大收益问题是背包问题的拓展应用之一它描述了在给定时间段内，买卖股票以最大化收益的问题该问题可以看作是一种特殊的背包问题，其中物品是股票，价值是股票的价格，重量是购买股票所需的时间股票交易的最大收益问题描述问题描述举例给定一个数组，表示第天的股票价格你最例如，假设，那么你所prices prices[i]i prices=[7,1,5,3,6,4],k=2多可以完成笔交易（买入和卖出算作一次交易）设计一个能获得的最大利润为（买入第天，卖出第天，再买入k724算法来计算你所能获得的最大利润第天，卖出第天）56股票交易的最大收益动态规划求解定义状态1表示第天完成笔交易，且当天没有持股的dp[i][k]

[0]i k最大收益状态转移方程2dp[i][k]

[0]=maxdp[i-1][k]

[0],dp[i-1][k]

[1]+prices[i]边界条件3dp

[0][k]

[0]=0,dp[i]

[0]

[0]=0股票交易的最大收益状态定义状态意义状态定义代表了在考虑前天的股票价格，最多完成笔交dp[i][k]

[0]i k表示第天完成笔交易，且当天没有持股的最大易的情况下，当天没有持股所能得到的最大收益dp[i][k]

[0]i k收益股票交易的最大收益状态转移方程dp[i][k]

[0]=maxdp[i-1][k]

[0],dp[i-1][k]

[1]+prices[i]表示第天完成笔交易，且当天没有持股的最大收益1i kdp[i-1][k]

[0]2表示第天完成笔交易，且当天没有持股的最大收益i-1kdp[i-1][k]

[1]+prices[i]3表示第天完成笔交易，且当天持有股票，并在第天i-1ki卖出股票，所能得到的最大收益股票交易的最大收益优化空间优化时间优化由于只依赖于和可以使用贪心算法进行时间优化，但贪心算法不一定能得到最优dp[i][k]

[0]dp[i-1][k]

[0]dp[i-，因此可以使用滚动数组进行空间优化，将三维数组压解1][k]

[1]缩为二维数组12最长公共子序列最长公共子序列问题是背包问题的拓展应用之一它描述了从两个字符串中找出最长的公共子序列的问题该问题可以看作是一种特殊的背包问题，其中物品是字符串的字符，价值是字符的长度，重量是字符在字符串中的位置最长公共子序列问题描述问题描述举例给定两个字符串和，找出这两个字符串的最长公例如，那么这两个字符串的text1text2text1=abcde,text2=ace,共子序列的长度最长公共子序列是，长度为ace3最长公共子序列动态规划求解定义状态1表示的前个字符和的前个字符dp[i][j]text1i text2j的最长公共子序列的长度状态转移方程2dp[i][j]=maxdp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1边界条件3dp

[0][j]=0,dp[i]

[0]=0最长公共子序列状态定义状态定义表示的前个字符和的前个字符的最长公共dp[i][j]text1i text2j子序列的长度状态意义代表了在考虑的前个字符和的前个字dp[i][j]text1i text2j符时，所能得到的最大长度的公共子序列最长公共子序列状态转移方程dp[i][j]=maxdp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1表示的前个字符和的前个字符的最长公共子序列的长度1text1i text2jdp[i-1][j]2表示的前个字符和的前个字符的最长公共子序列的长度text1i-1text2jdp[i][j-1]3表示的前个字符和的前个字符的最长公共子序列的长度text1i text2j-1dp[i-1][j-1]+14表示的前个字符和的前个字符的最长公共子text1i-1text2j-1序列的长度，再加上（因为）1text1[i-1]==text2[j-1]最长公共子序列优化空间优化时间优化由于只依赖于、dp[i][j]dp[i-1][j]和，因此12最长公共子序列问题的时间复杂度为dp[i][j-1]dp[i-1][j-1]可以使用滚动数组进行空间优化，将二，无法进行进一步优化On*m维数组压缩为一维数组动态规划的核心思想总结最优子结构问题的最优解包含子问题的最优解无后效性子问题的求解不会影响其他子问题的求解状态定义定义合适的中间状态，以记录子问题的最优解状态转移方程描述状态之间的关系，以递推地求解最优解动态规划求解背包问题的应用场景货车装载根据货车容量和货物价值，选择装载哪些货物投资组合优化在有限的资金预算下，选择哪些股票或债12以获得最大利润券以最大化投资回报项目管理根据项目预算和资源，选择哪些项目进行投资资源分配根据资源限制，选择哪些任务进行分配以获得34以获得最大的经济效益最大的收益最优解的求解动态规划可以有效地求解一些组合优化问策略决策动态规划可以帮助我们制定最优策略，例如在56题，例如背包问题、最长公共子序列问题、最短路径问题博弈论中，动态规划可以用于制定最优的行动策略等等动态规划求解背包问题的常见问题及解决方案空间复杂度时间复杂度动态规划算法通常需要使用二维动态规划算法的时间复杂度通常数组来存储状态，因此空间复杂为，其中是物品数OnW n度较高可以尝试使用滚动数组量，是背包容量可以尝试W进行空间优化，将二维数组压缩使用单调队列等方法进行时间优为一维数组化状态转移方程状态转移方程是动态规划算法的核心需要仔细推导状态转移方程，并保证其逻辑正确。