计算机科学、算法设计和优化理论中非常著名的“背包问题”（Knapsack Problem）是一个典型的组合优化问题，也是动态规划算法的一个经典应用。
背包问题有多种变体，但最基本的形式是：
给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择装入背包的物品，使得背包内物品的总价值最大。
0-1背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
暴力解法应该是怎么样的呢？
每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。
背包最大重量为4。
物品为：
物品
重量
价值
0
1
15
1
3
20
2
4
30
问背包能背的物品最大价值是多少？
确定dp数组以及下标的含义：
需要使用二维数组，为什么呢？因为有两个维度需要表示，分别是：物品 和 背包容量
那么这里 i,j,dp[i][j] 分别表示什么呢？
i 来表示物品、j表示背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
确定递推公式
对于递推公式，首先我们要明确有哪些方向可以推导出 dp[i][j]。
不放物品i：由dp[i - 1][j]推出，此时dp[i][j]就是dp[i - 1][j]。
放物品i：由dp[i - 1][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])
dp数组如何初始化
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
再看状态转移方程 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物品。
确定遍历顺序
有两个遍历的维度：物品与背包重量
这里降维会逆序，要理解
举例推导dp数组
46. 携带研究材料（第六期模拟笔试）
二维dp代码如下：
12345678910111213141516171819202122232425262728293031def fun(n, weights, vals): nums, bag = n[0], n[1] # dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少 dp = [[0] * (bag + 1) for _ in range(nums)] # 背包容量j为0的话，即dp[i][0] = 0 # dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值 for j in range(weights[0], bag + 1): print(j) dp[0][j] = vals[0] print(dp) # dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) for i in range(1, nums): for j in range(bag + 1): if j < weights[i]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + vals[i]) print(dp) return dp[-1][-1]if __name__ == '__main__': # n, weight, vals = ([int(x) for x in input().split()], # [int(x) for x in input().split()], # [int(x) for x in input().split()]) n = [6, 1] weights = [2, 2, 3, 1, 5, 2] vals = [2, 3, 1, 5, 4, 3] print(fun(n, weights, vals)) # 5
优化成一维dp：
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。即dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
为什么呢？
倒序遍历是为了保证物品i只被放入一次！如果一旦正序遍历了，那么物品0就会被重复加入多次！
123456789101112131415161718# https://kamacoder.com/problempage.php?pid=1046def fun(): n, weight, vals = ([int(x) for x in input().split()], [int(x) for x in input().split()], [int(x) for x in input().split()]) nums, bag = n[0], n[1] dp = [0] * (bag + 1) for j in range(weight[0], bag + 1): dp[j] = vals[0] for i in range(1, nums): for j in range(bag, weight[i] - 1, -1): dp[j] = max(dp[j], dp[j - weight[i]] + vals[i]) return dp[bag]if __name__ == '__main__': print(fun())
416. 分割等和子集 - 力扣（LeetCode）
当做01背包做，总容量是已知的
当某个dp达到target后，就填满了背包
执行用时分布1993ms，击败26.68%
消耗内存分布38.73MB，击败5.89%
1234567891011121314151617181920212223242526class Solution(object): def canPartition(self, nums): # 1 - 100 total = sum(nums) if total % 2: return False target = total // 2 length = len(nums) # 总容量是target # 重量和价值都是num # 背包满时即为一个子集 # 另一个是剩下的就行 dp = [[0] * (target + 1) for _ in range(length)] # dp[i][j]表示背包容量为j时从0-i中任取所得到的最大总和 # dp[0][j] 表示背包容量为j时从0中任取所得到的最大总和 for j in range(nums[0], target + 1): dp[0][j] = nums[0] for i in range(1, length): for j in range(target + 1): if j < nums[i]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]) if dp[i][j] == target: return True return False
降维：
这里可以思考下为什么遍历变成倒序了
依旧正序是错误的，127 / 143 个通过的测试用例
12345678910111213141516171819202122class Solution(object): def canPartition(self, nums): # 1 - 100 total = sum(nums) if total % 2: return False target = total // 2 length = len(nums) dp = [0] * (target + 1) # dp[j]表示背包容量为j时从0-i中任取所得到的最大总和，i被降维了，滚动数组 # dp[j] 表示背包容量为j时从0中任取所得到的最大总和 for j in range(nums[0], target + 1): dp[j] = nums[0] for i in range(1, length): for j in range(target + 1): if j < nums[i]: dp[j] = dp[j] else: dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) if dp[j] == target: return True return False
如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
倒序后：
执行用时分布1518ms，击败71.56%
消耗内存分布12.13MB，击败51.08%
123456789101112131415161718192021class Solution(object): def canPartition(self, nums): # 1 - 100 total = sum(nums) if total % 2: return False target = total // 2 length = len(nums) dp = [0] * (target + 1) for j in range(nums[0], target + 1): dp[j] = nums[0] for i in range(1, length): for j in range(target, -1, -1): if j < nums[i]: dp[j] = dp[j] else: dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) if dp[j] == target: return True return False
去掉了没有变化的dp[j] = dp[j]
执行用时分布1579ms，击败70.24%
消耗内存分布11.97MB，击败76.67%
12345678910111213141516171819class Solution(object): def canPartition(self, nums): # 1 - 100 total = sum(nums) if total % 2: return False target = total // 2 length = len(nums) dp = [0] * (target + 1) for j in range(nums[0], target + 1): dp[j] = nums[0] for i in range(1, length): for j in range(target, -1, -1): if j >= nums[i]: dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) if dp[j] == target: return True return False
1046. 最后一块石头的重量 - 力扣（LeetCode）
用堆做
1234567891011121314151617class Solution(object): def lastStoneWeight(self, stones): hq = [] for s in stones: heapq.heappush(hq, -s) while hq: v1 = -heapq.heappop(hq) if not hq: return v1 v2 = -heapq.heappop(hq) if v1 != v2: heapq.heappush(hq, -abs(v1 - v2)) return 0
执行用时分布15ms，击败63.38%
消耗内存分布11.46MB，击败43.66%
v1 v2的大小关系是已知的，没必要用绝对值abs()
以及堆的初始化可以更简单
123456789101112131415class Solution(object): def lastStoneWeight(self, stones): hq = [-s for s in stones] heapq.heapify(hq) while hq: v1 = -heapq.heappop(hq) if not hq: return v1 v2 = -heapq.heappop(hq) if v1 != v2: heapq.heappush(hq, v2 - v1) return 0
1049. 最后一块石头的重量 II - 力扣（LeetCode）
提示：
把最终的答案看作是权重的总和，每个权重前面都有+或-符号。实际上，每个符号的和都是1。
使用动态规划:对于每一个可能的和N颗石头，这些和+x或-x可能与N+1颗石头，其中x是最新的石头的值。(这将多算全部为正或全部为负的总和，但这些都无关紧要。)
和分割子集完全一个思路捏
执行用时分布34ms，击败53.47%
消耗内存分布11.39MB，击败86.12%
123456789101112131415161718class Solution(object): def lastStoneWeightII(self, stones): total = sum(stones) target = total // 2 # 总容量是target # 重量和价值都是stone dp = [0] * (target + 1) # dp[j]表示背包容量为j时从0-i中任取所得到的最大总和，i被降维了，滚动数组 # dp[j] 表示背包容量为j时从0中任取所得到的最大总和 for j in range(stones[0], target + 1): dp[j] = stones[0] for i in range(1, len(stones)): for j in range(target, -1, -1): if j >= stones[i]: dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]) # print(dp) return total - 2 * dp[-1]
494. 目标和 - 力扣（LeetCode）
可以回溯法硬解，但为什么它也可以是背包？
首先，确实对于每一个num都有两种选择，取正或负
dp = [0] * (m + 1) 和 dp[0] = 1：
创建一个长度为 m + 1 的列表 dp，用于存储不同和值的组合数。
初始化 dp[0] 为 1，表示空集的和为 0，只有一种方法。
两层循环：
外层循环遍历数组 nums 中的每个元素。
内层循环从 m 倒序遍历到 0。
如果当前和值 j 大于等于当前数组元素 nums[i]，说明可以选择当前元素加入子集中，此时 dp[j] 的值等于不选择当前元素的组合数（即 dp[j]）加上选择当前元素的组合数（即 dp[j - nums[i]]）。
执行用时分布39ms，击败77.99%
消耗内存分布11.30MB，击败95.60%
474. 一和零 - 力扣（LeetCode）
执行用时分布1586ms，击败65.91%
消耗内存分布11.55MB，击败74.93%
01背包，但是物品重量有两个维度
1234567891011121314class Solution(object): def findMaxForm(self, strs, m, n): # m个0, n个1 dp = [[0] * (n + 1) for _ in range(m + 1)] # dp[i][j]表示有i个0，j个1的满足条件的最大组合数 for s in strs: c0 = s.count('0') c1 = len(s) - c0 print("c0", c0, "c1", c1) for i in range(m, c0 - 1, -1): for j in range(n, c1 - 1, -1): dp[i][j] = max(dp[i][j], dp[i - c0][j - c1] + 1) print(dp) return dp[-1][-1]
完全背包问题
问题描述：与0-1背包问题类似，但每种物品的数量是无限的。
解法：同样使用动态规划，但状态转移方程有所不同。由于每种物品可以无限次使用，因此在更新dp[i][j]时，需要考虑从dp[i-1][j]（不选第i个物品）和dp[i][j-wt[i]]+val[i]（选择第i个物品，且假设之前已经选择了足够的空间来放下它）中选择较大的值。
多重背包问题
每种物品有一定数量的限制。
分组背包问题
物品被划分为若干组，每组中的物品互斥（即每组中最多只能选一个物品），求解最优解。
二维背包问题：除了重量和价值外，还考虑了其他维度的限制（如体积、时间等）。
记忆中的背包 - BZOJ 4971 - Virtual Judge
构造