代码随想录第30天：动态规划3

一、01背包理论基础（Kama coder 46）

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

1. 确定dp数组以及下标的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 确定递推公式：

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。

• 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，

• dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，

• 所以dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

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

3. dp数组如何初始化：

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

4. 确定遍历顺序：先遍历物品和先遍历背包都可以！！ 但是先遍历物品更好理解。

n, bagweight = map(int, input().split())  # 输入物品数量和背包容量weight = list(map(int, input().split()))  # 输入物品的重量
value = list(map(int, input().split()))   # 输入物品的价值# 初始化 dp 数组，大小为 n 行 bagweight + 1 列
dp = [[0] * (bagweight + 1) for _ in range(n)]# 初始化第一行，即只有第一个物品时的情况
for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]# 动态规划填充 dp 数组
for i in range(1, n):for j in range(bagweight + 1):if j < weight[i]:dp[i][j] = dp[i - 1][j]  # 当前容量不足以放入物品 i，保持上一行的值else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])  # 选择放或不放物品 i# 输出最终结果
print(dp[n - 1][bagweight])  # 最大价值

1.关于DP数组初始化的大小：

在背包问题中，物品的索引从 0 到 n-1，而不是从 1 到 n。因此，如果你用 n 个物品，那么 dp 数组的大小应该是 n x (bagweight + 1)。

• 行数（物品数）： 我们有 n 个物品，因此使用 n 行来表示每个物品。

• 列数（背包容量）： 背包的容量从 0 到 bagweight，所以需要 bagweight + 1 列。

因此，初始化 dp数组为：

dp = [[0] * (bagweight + 1) for _ in range(n)]

2.为什么不使用 (n + 1) x (bagweight + 1)？

如果使用 (n + 1) 行，而不是 n 行，实际上会多出一行。多出来的 dp[n][j] 并不会直接影响到最终结果，但它表示的状态是多余的，因为你只需要 n 行来表示 n 个物品的情况。dp[n][j] 是你已经处理过的所有物品的情况，所以对它没有额外的意义。

但 在 dp[i][j] 中，我们是以物品的数量 i 来计算状态的，所以我们可以将“没有物品”的情况作为 dp[0][j] 这一行来处理：

• dp[0][j] 表示没有任何物品时，背包容量为 j 时的最大价值。这时，最大价值是 0，所以 dp[0][j] 全部初始化为 0。

• 空间浪费： 多余的一行并不会影响最终结果，但增加了内存使用。

• 冗余状态： dp[n][j] 是多余的，并且它并不会在求解过程中被有效利用。

二、01背包理论基础（滚动数组）

在使用二维数组的时候，可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式变成：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);那么与其把dp[i - 1]这一层拷贝到dp[i]上，不如直接使用一个一维数组。

# 输入物品个数n和背包容量bagweight
n, bagweight = map(int, input().split())  # 输入每个物品的重量
weight = list(map(int, input().split()))  # 输入每个物品的价值
value = list(map(int, input().split()))  # 创建一个一维数组dp，dp[j] 表示背包容量为j时的最大价值，初始值为0
dp = [0] * (bagweight + 1)  # 初始化dp[0] = 0，背包容量为0时的最大价值是0
dp[0] = 0  # 遍历所有物品
for i in range(n):  # 从大到小遍历背包容量，确保每个物品只被放入一次for j in range(bagweight, weight[i] - 1, -1):  # 更新当前背包容量j的最大价值# max(当前背包容量j不放物品i的价值, 当前背包容量j放物品i的价值)dp[j] = max(dp[j], dp[j - weight[i]] + value[i])  # 最终输出背包容量为bagweight时的最大价值
print(dp[bagweight])  

for j in range(bagweight, weight[i] - 1, -1):  

倒序遍历是为了保证物品i只被放入一次，正序遍历会导致物品被重复加入多次！

例如：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

遍历顺序：只能先遍历物品后遍历背包，因为背包遍历时由大到小逆序的，如果先遍历背包容量，那么每个dp[j]就只会放入一个物品。

可以看出，一维dp数组的解法，代码简洁，而且空间复杂度还降低了一个数量级！

三、分割等和子集（Leetcode 416）

1. 确定dp数组以及下标的含义：如果背包所载重量为target， dp[target]就是装满 背包之后的总价值，因为 本题中每一个元素的数值既是重量，也是价值

2. 确定递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

3. dp数组初始化：本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0

4. 确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历

5.dp[j]的数值一定是小于等于j的。

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和 j 。

class Solution:def canPartition(self, nums: List[int]) -> bool:total = sum(nums)#题目描述1 <= nums.length <= 200  1 <= nums[i] <= 100，#total//2最大为200*100/2=10000dp = [0] * 10001  # dp[i]表示能否凑出总和为i的子集if total % 2 != 0:return False  # 如果总和是奇数，不能平分target = total // 2  # 目标是找到一个和为total//2的子集# 0-1背包问题for num in nums:# 从大到小遍历，保证每个物品只能使用一次for j in range(target, num - 1, -1):dp[j] = max(dp[j], dp[j - num] + num)  # 当前背包容量j的最大值if dp[target] == target:  # 如果能找到和为target的子集return Truereturn False

class Solution:def canPartition(self, nums: List[int]) -> bool:# 计算数组所有元素的和total_sum = sum(nums)# 如果总和是奇数，无法均分为两个相等的部分if total_sum % 2 != 0:return False# 目标是寻找一个子集，使得其和为total_sum // 2target_sum = total_sum // 2# dp[i] 表示是否可以找到和为i的子集dp = [False] * (target_sum + 1)dp[0] = True  # 0总是可以被表示为一个空子集# 遍历数组中的每个元素for num in nums:# 从target_sum逆序迭代到num，步长为-1，防止重复使用当前元素for i in range(target_sum, num - 1, -1):dp[i] = dp[i] or dp[i - num]  # 如果dp[i-num]为True，表示可以组成ireturn dp[target_sum]  # 返回能否找到和为target_sum的子集

 dp[i] = dp[i] or dp[i - num]

• 初始时，dp[0] = True，因为空集的和为 0。

• 对于每个物品 num，我们尝试更新 dp[i]。

  假设我们已经知道某个子集的和为 i - num，那么如果我们再加入物品 num，就可以得到和为 i 的子集。所以我们用 dp[i - num] 来检查是否可以构造出和为 i 的子集。

四、最后一块石头的重量II（Leetcode 1049）

思路：一堆的石头重量是sum，那么我们就尽可能拼成 重量为 sum / 2 的石头堆。 这样剩下的石头堆也是 尽可能接近 sum/2 的重量。问题转化为：有一堆石头，每个石头都有自己的重量，是否可以装满最大重量为 sum / 2 的背包。

1. 确定dp数组以及下标的含义:dp[j] 表示重量为 j 的背包，最多可以背最大重量为dp[j]。

2. 确定递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

3.dp数组初始化：

提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 100，所以最大重量就是30 * 100 。

而我们要求的target其实只是最大重量的一半，所以dp数组开到1500大小

4. 确定遍历顺序：先遍历物品后遍历背包，且背包倒序遍历

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:total = sum(stones)  # 计算所有石头的总和dp = [0] * 1501  # 初始化 dp 数组，用于记录背包的状态target = total // 2  # 目标是求两堆石头的和尽量相等# 动态规划遍历每块石头for stone in stones:for j in range(target, stone - 1, -1):  # 从 target 到 stone 遍历，保证每个石头只能使用一次dp[j] = max(dp[j], dp[j - stone] + stone)# 返回最终结果，total - 2 * dp[target] 是求两堆石头的差return total - dp[target] * 2

dp[target] 代表能够凑成的最接近一半总和的子集的重量。剩下的石头重量为total -dp[target]，两堆石头的差值为total - dp[target] - dp[target] = total - dp[target] * 2 

本题与分割等和子集基本一样。