参考/优秀博客

定义

给定一个背包容量为target，给一个数组nums，按一定方式，选取nums中的元素得到target。 根据定义，我们可以将问题分成不同类型。

类型

  • 基本型：
    1. 0/1背包：每个物品最多选择一次
    2. 多重背包：每个物品最多选择k次（可以看做k个0/1背包，这里不单列出来说了）
    3. 完全背包：每个物品不限制选择次数
  • 组合型：考虑拿取物品的顺序，相同物品，不同拿取顺序表示不同的结果
    1. 组合背包+0/1背包
    2. 组合背包+多重背包 ==> 组合背包+0/1背包
    3. 组合背包+完全背包
  • 分组型：不止一个背包，这里只有一倒例题，可以直接去看例题

模板

基础模板

对于所有的背包问题，先看原始背包的解题思路和代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
weight = [None]*n
values = [None]*n

# dp[i][j]: 从索引为0-i的物品中选择不超过j重的物品的最大价值

dp = [[0]*n for _ in range(target)]   # 初始化
for j in range(weight[0],target+1):   # 第0行表示选择第0个物品的最大价值
  dp[0][j] = value[0]

for i in range(1,n):              # 遍历物品
  for j in range(target):     # 遍历背包容量
    if j < weight[i]:             # 如果背包容量已经不足以拿下第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])

上述代码可以优化成一维：

1
2
3
4
5
# dp[j]: 容量为j的背包能放下东西的最大价值
dp = [0]*target
for i in range(n):  # 遍历物品
  for j in range(weight[i],target+1)[::-1]:   # 遍历背包容量(一定要逆序，如果顺序的话，dp[j-weight[i]]这个值可能是这一轮更新过的值，就不是上一轮结束的值了)
    dp[j] = max(dp[j],dp[j-weight[i]]+value[i])

整合模板：

1
2
3
4
5
6
7
    __纯0/1背包:  外weight，内target，target倒序且>=weight[i]
__ |
   |__纯完全背包：外weihgt，内target，target正序且>=weight[i]

    __组合+0/1背包:  外target，内weight，target倒序且>=weight[i]
__ |
   |__组合+完全背包：外target，内weight，target正序且>=weight[i]

我们观察上面的结果，只要记住三条就行：
(1). 首先记住纯0/1背包
(2). 遇到完全背包，target变正序
(3). 遇到组合背包，调换内外for循环

目标求解

一般目标求解为下面三种：

  • 最值问题：
    • dp[i]=max/min (dp[j],dp[j-weight[i]]+1)
    • dp[i]=max/min (dp[j],dp[j-weight[i]]+value[i])
  • 存在问题：
    • dp[i] = dp[i] or dp[i-weight[i]]
  • 个数问题：
    • dp[i] += dp[i-weight[i]]

遇到背包问题的做题顺序

  1. 先考虑是否可以转换为背包问题
  2. 判断是0/1背包还是完全背包
  3. 判断是否附加组合要求

LeetCode中背包问题

题目 类型
322.零钱兑换 纯完全背包+最值问题
416.分割等和子集 纯0/1背包+存在性问题
494.目标和 组合+0/1背包+个数问题
279.完全平方数 完全背包+最值问题
377.组合总和 Ⅳ 组合+完全背包+个数问题
518.零钱兑换 II 纯完全背包+个数问题
1049.最后一块石头的重量II 纯0/1背包+最值问题
1155.掷骰子的N种方法 分组背包