当前位置：首页 > news >正文

算法训练营第三十天 | 动态规划（三）

news 来源：原创 2025/6/30 14:54:42

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

一、01背包问题理论基础（一）
动态规划五部曲
确定dp数组以及下标的含义
确定递推公式
初始化dp数组
确定遍历顺序

二、01背包问题理论基础（二）
动态规划五部曲
确定dp数组以及下标的含义
确定递推公式
初始化dp数组
确定遍历顺序
代码

三、Leetcode 416. 分割等和子集
动态规划五部曲
确定dp数组以及下标的含义
确定递推公式
初始化dp数组
确定遍历顺序

代码

一、01背包问题理论基础（一）

有n件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划五部曲

确定dp数组以及下标的含义

这里我们使用二维数组 dp[i][j]。其中 i 代表物品，j 代表背包。

dp 数组表示的含义是，当背包重量为 j 时，我们从 0 到 i 个物品中进行取舍，能获得的最大价值。

本题中 dp 数组的定义十分关键！

确定递推公式

当我们背包重量为 i 的时候，我们一共有两种情况。

背包重量小于物品 i 的重量时，我们无法放入物品，所以我们直接继承上一个状态 dp[i-1][j] ，也就是当背包重量为 j 时，我们从 0 到 i-1 个物品中进行取舍，能获得的最大价值。
当背包重量大于物品 i 的重量时，我们有两种选择，考虑是否选择将物品 i 放入背包内。

不将物品 i 放入背包内，此时我们也是继承上一个状态 dp[i-1][j]。
将物品 i 放入背包内，此时的状态应为：当前背包容量减去物品 i 的重量在 0 到 i-1 个物品中任意取的最大值再加上物品 i 的价值。，即 dp[i][j] = dp[i - 1][j - weight[i]] + value[i]

我们的目的是获得最大的价值，所以当背包重量大于物品 i 的重量时，我们对两种情况取最大值 max(dp[i - 1][j - weight[i]] + value[i], dp[i-1][j])。

最后得出递推公式：

if weight[i-1] > j:dp[i][j] = dp[i-1][j]
else:dp[i][j] = max[dp[i - 1][j - weight[i]] + value[i], dp[i-1][j]]

初始化dp数组

将二维数组理解成为一个表格，行代表物品，列代表背包重量。

我们当前要计算的表格是通过左上方的表格递推出来的，所以我们要对第一列和第一行进行初始化。

第一行代表的是，当背包重量为 j 时，对第一个物品进行取舍，我们能得到的最大价值。
这时我们只有一个物品可以考虑，所以向右遍历，当物品的重量大于等于背包重量时，表示这个物品可以放进背包内，这时右面的表格就初始化为第一个物品的价值。左面的表格就初始化为 0。

第一列代表的是，当背包重量为 0 时，对前 i 个物品进行取舍能获得的最大价值。背包重量是 0，当然什么物品也放不进去，所以第一列全部初始化为 0。

其余位置都是通过递推公式计算得出，所以初始值无所谓，全部初始化为 0。

确定遍历顺序

很显然，我们需要两层 for 循环，那么到底是先遍历物品还是先遍历背包呢？

本题中先遍历背包和先遍历物品都可以！

先遍历物品的方式更符合动态规划的自底向上的求解思路。先考虑只有一个物品时，对于不同背包容量的最大价值，然后逐步增加物品数量，计算在当前物品加入的情况下，不同背包容量的最大价值。这种方式可以清晰地看到状态是如何逐步转移和构建的
先遍历背包的方式则是先固定背包容量，然后看在这个容量下，不同物品组合能达到的最大价值。虽然代码执行顺序不同，但最终也能正确计算出所有状态的最大价值。

代码：

n, bagweight = map(int, input().split())weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [[0] * (bagweight + 1) for _ in range(n)]for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]for i in range(1, n):for j in range(bagweight + 1):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])print(dp[n - 1][bagweight])

二、01背包问题理论基础（二）

对于递归问题，有的时候我们当前状态只是通过前面几个状态进行推导，如果定义一个很长的数组，那么大部分的空间是被浪费的，滚动数组就是在空间上进行优化的一种方法。

举一个例子，斐波那契数列问题。我们的状态转移方程是 dp[i]=dp[i-1]+dp[i-2 。那么当前状态是由前两个状态推导而来，当我们推导 dp[3] 的时候，dp[0] 就已经用不到了，所以我们完全可以将推导得到的 dp[3] 放在 dp[0] 的位置，这样我们只开辟了三块空间就能完成整个计算，大大节省了空间，这就是滚动数组的思想。

对于 01 背包问题，我们当前层的状态都是由上一层的状态推导而来，所以也可以使用滚动数组来进行优化。

动态规划五部曲

确定dp数组以及下标的含义

dp[j] 表示背包重量为 weightp[j] 时，可以获得的最大价值。

确定递推公式

二维dp数组的递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
一维dp数组，其实就上一层 dp[i-1] 这一层拷贝的 dp[i]来。
所以在上面递推公式的基础上，去掉i这个维度就好。

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

以下为分析：

dp[j] 为容量为j的背包所背的最大价值。

dp[j] 可以通过 dp[j] - weight[i]] 推导出来，dp[j] - weight[i]] 表示容量为 j - weight[i] 的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示容量为 [j - 物品i重量] 的背包加上物品 i 的价值。（也就是容量为 j 的背包，放入物品 i 了之后的价值即：dp[j] ）

此时 dp[j] 有两个选择，一个是取自己 dp[j] 相当于二维dp数组中的 dp[i-1][j] ，即不放物品 i，一个是取 dp[j - weight[i]] + value[i] ，即放物品 i ，指定是取最大的，毕竟是求最大价值。

初始化dp数组

dp数组初始化的时候，都初始为 0 即可。

确定遍历顺序

我们在二维dp数组的时候，遍历顺序没有要求，但是对于一维数组，这里有严格的顺序。
我们的滚动数组的思想是当前层是由上一层拷贝而来，而每一层代表的是物品，所以我们要先便遍历物品，再遍历背包重量。

在遍历背包重量的时候，一定要倒序遍历。

因为在某一层，当前数值是由他左面推导而来，如果我们正序遍历的话，新的值会覆盖掉原来的值，这样也就导致了某一个物品被多次使用。

代码

n, bagweight = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [0] * (bagweight + 1)  # 创建一个动态规划数组dp，初始值为0dp[0] = 0  # 初始化dp[0] = 0,背包容量为0，价值最大为0for i in range(n):  # 应该先遍历物品，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品for j in range(bagweight, weight[i]-1, -1):  # 倒序遍历背包容量是为了保证物品i只被放入一次dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagweight])

三、Leetcode 416. 分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

引用：

原文链接：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/description/
视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE/

解决的问题是判断集合里能否出现总和为 sum / 2 的子集，这相当于有一个只能装重量为 sum / 2 的背包，商品就是集合里的数字，要判断这些数字能否把背包装满。
对于这些数字商品而言，它们只有一个维度，即重量等于价值。当这些数字能装满承载重量为 sum / 2 的背包时，背包的价值也为 sum / 2。
所以此问题可转化为装满承载重量为 sum / 2 的背包时，其最大价值是多少，若最大价值是 sum / 2，就说明背包正好被商品装满，由于商品是数字且重量和价值相同，因此可以直接用 01 背包来解决这个问题。

动态规划五部曲

确定dp数组以及下标的含义

dp[j] 表示背包重量为 weightp[j] 时，可以获得的最大价值。

确定递推公式

背包问题的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
那么这里重量和价值在同一个维度，所以我们的递推公式改写为
dp[j]=max(dp[j], dp[j-nums[i]]+nums[i])

初始化dp数组

dp数组初始化的时候，都初始为 0 即可。

确定遍历顺序

和我们01背包问题中的一维滚动数组遍历方式一样。

代码

class Solution:def canPartition(self, nums: List[int]) -> bool:total_sum = sum(nums)if total_sum % 2 != 0:return Falsetarget = int(total_sum / 2)dp = [0] * (target+1)for i in range(len(nums)):for j in range(target, nums[i]-1, -1):dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])return dp[target]==target

文章目录

一、01背包问题理论基础（一）

动态规划五部曲

确定dp数组以及下标的含义

确定递推公式

初始化dp数组

确定遍历顺序

二、01背包问题理论基础（二）

动态规划五部曲

确定dp数组以及下标的含义

确定递推公式

初始化dp数组

确定遍历顺序

代码

三、Leetcode 416. 分割等和子集

动态规划五部曲

确定dp数组以及下标的含义

确定递推公式

初始化dp数组

确定遍历顺序

代码

相关文章：