代码随想录第33天：动态规划6（完全背包基础）
一、完全平方数（Leetcode 279）
本题与“零钱兑换”基本一致。
1.确定dp数组以及下标的含义
dp[j]：和为j的完全平方数的最少数量为dp[j]
2.确定递推公式
dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
3.dp数组初始化
dp[ 0 ]= 0
4.遍历顺序
求组合先物品后背包，求排列先背包后物品
本题求最小次数，哪种顺序都可以，习惯先物品后背包
class Solution:def numSquares(self, n: int) -> int:# 初始化 dp 数组，长度为 n+1，初始值为正无穷（表示无法凑出）# dp[i] 表示凑出数字 i 所需的最少完全平方数数量dp = [float('inf')] * (n + 1)# 凑出数字 0 所需的完全平方数个数为 0dp[0] = 0# 枚举所有可能的完全平方数 i*i（i 从 1 到 sqrt(n)）for i in range(1, int(n ** 0.5) + 1):square = i * i # 当前的完全平方数# 更新所有大于等于当前平方数的 dp[j]for j in range(square, n + 1):# 状态转移方程：dp[j] 最小为 dp[j - square] + 1dp[j] = min(dp[j], dp[j - square] + 1)# 返回凑出 n 的最少完全平方数个数return dp[n]
二、单词拆分（Leetcode 139）
1.确定dp数组以及下标的含义
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
2.确定递推公式
if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
3.dp数组初始化
dp[ 0 ]= True
dp = [False] * ( len(s) + 1 )
4.遍历顺序
求组合先物品后背包，求排列先背包后物品
本题物品放入背包是有顺序的，等价于排列问题，所以先遍历背包后遍历物品
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict) # 优化查找效率dp = [False] * (len(s) + 1)dp[0] = True # 空字符串可以被组成for i in range(1, len(s) + 1):for j in range(i):if dp[j] and s[j:i] in wordSet:dp[i] = Truebreak # 找到一个可拆分位置即可跳出return dp[len(s)]
三、多重背包理论基础（Kamacoder 56）
有 N 种物品和一个容量为 V 的背包。第i种物品最多有 Mi 件可用，每件耗费的空间是 Ci ，价值是 Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包类似，我们只需要将 Mi 件摊开，变成多个“单件的物品”，就转换为01背包问题了。
例如：
-
你有一种物品 A，重量为 2，价值为 5，你有 13 个 A。
-
背包容量为 20。
-
你不能像完全背包那样无限放入 A，也不能像 0-1 背包那样只选一个 A。
-
你最多只能选 13 个 A，如何放入这些 A，使得价值最大？
为什么不能直接暴力？
for i in range(N): # 遍历每种物品for j in range(C, w[i], -1): # 遍历背包容量for k in range(1, nums[i] + 1): # 枚举每种物品的个数if k * w[i] <= j:dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])
这种写法的时间复杂度是 O(N * C * M)，其中 M 是物品最大数量。如果 M 很大，比如 10^5，就会超时。
1.解决办法：二进制拆分优化
原理：任何一个正整数都可以用不重复的二进制数之和表示。例如：
-
13 = 1 + 2 + 4 + 6（剩余部分）
-
19 = 1 + 2 + 4 + 8 + 4（最后一个4是19-15）
⛳ 也就是说，我们可以把
13个物品拆分成若干批次：1个、2个、4个、剩下6个物品。
原始数量：13
k = 1 -> 拆出 1 个
剩余 = 12
k = 2 -> 拆出 2 个
剩余 = 10
k = 4 -> 拆出 4 个
剩余 = 6
k = 8 -> 拆不出8个（超过了），所以拆出剩下的 6 个
完成拆分：1, 2, 4, 6（共13个）
问题：
-
背包容量 C = 10
-
有一种物品：重量 = 2，价值 = 3，数量 = 5
你不能直接一次枚举 0~5 个的所有组合。我们改用二进制拆分优化。
拆分：
5 可以拆成 1, 2, 2（即 1 + 2 + 2 = 5）
那么我们等价于有 3 个 01背包物品：
-
一个重量 2，价值 3 的物品（1 个）
-
一个重量 4（2×2），价值 6（3×2）的物品（2 个）
-
一个重量 4，价值 6 的物品（再 2 个）
再用 0-1 背包处理这些分拆后的“独立物品”。
好处？
-
原来要枚举 0~5 的所有选择，共 6 种情况。
-
拆成二进制后，最多只需要
log2(数量)次枚举（时间复杂度从线性降到对数）。
# 读取输入：C 表示背包容量，N 表示物品种类数量
C, N = map(int, input().split())# 分别读取每个物品的重量、价值和数量
weights = list(map(int, input().split())) # 每个物品的重量
values = list(map(int, input().split())) # 每个物品的价值
nums = list(map(int, input().split())) # 每个物品的数量# 初始化一维 dp 数组，dp[j] 表示容量为 j 的背包可以获得的最大价值
dp = [0] * (C + 1)# 遍历每一个物品
for i in range(N):w, v, m = weights[i], values[i], nums[i] # 当前物品的重量、价值和数量k = 1 # 用于二进制拆分（从1开始，每次乘2）# 将物品数量 m 拆成多个 2 的幂形式（如 1, 2, 4, 8...），直到耗尽 mwhile m > 0:cnt = min(k, m) # 本次拆分出来的个数不能超过剩余数量 mm -= cnt # 减去本次已处理的数量# 将 cnt 个该物品当作一个“01背包物品”处理# 倒序遍历背包容量，确保每个物品只被使用一次（01背包）for j in range(C, w * cnt - 1, -1):dp[j] = max(dp[j], dp[j - w * cnt] + v * cnt) # 状态转移方程k <<= 1 # k *= 2，下一轮准备拆更大的 2 的幂# 最终输出背包容量为 C 时的最大价值
print(dp[-1])