[python刷题模板] 背包问题

• • 一、 算法&数据结构
  • • 1. 描述
    • 2. 复杂度分析
    • 3. 常见应用
    • 4. 常用优化
  • 二、 模板代码
  • • 0. 混合背包求最大/最小值模板(0-1/完全/多重)
    • 1. 分组背包求最大/最小值模板
    • 2. 01背包求方案数模板(完全背包也在，但没测)
    • 3. 分组背包求方案数
    • 6. 转化为01背包
  • 三、其他
  • 四、更多例题
  • 五、参考链接

一、 算法&数据结构

1. 描述

0-1背包:题意给出n种物品分别的体积v和价值w，背包的总容量vol，每种物品只能选0或1个，问背包里最多能装多少价值。
完全背包:题意给出n种物品分别的体积v和价值w，背包的总容量vol，每种物品能选无限个，问背包里最多能装多少价值。
多重背包:题意给出n种物品分别的体积v、价值w和个数c，背包的总容量vol，每种物品能选c[i]个，问背包里最多能装多少价值。
混合背包:一道题里给出的物品分别可能是上述三种的情况，混合讨论，这种比较简单，分类转移即可，不多讨论，但模板是按这个写。
分组背包:题意给出n'组'物品，每组里有c种物品，每组只能选或不选1个物品，问背包里最多能装多少价值。
二维费用背包:一般是0-1背包的变种，给出的物品多了个重量，背包也有负重上限。简言之就是多了个维度。以上所有问题还可以变成问方案数。

• 以上就是常见的几种背包题目，以下暂不讨论二维费用背包了，如果讨论会明确指出。
• 01背包是最简单的背包入门，正常状态定义是二维：f = [[0]*(vol+1) for _ in range(n+1)] ，其中vol是背包容积，n是物品数。
  • 定义:f[i][j]为尝试了前i个物品，选的总体积为j时的最大价值。实现时一般把i+1偏移一位。
  • 转移:考虑当前物品选或不选：不选f[i][j] = f[i-1][j];选f[i][j] = f[i-1][j-v]+w。
  • 初始:f[0][0]=0，即一个不选价值是0(如果是问方案数则f[0][0]=1,表示一个不选的方案数只有1个)。
  • 答案:若是问不超过背包容量则max(f[n])；若是问恰好容量j的情况则f[n][j]。
  • 实现时，01背包可以倒序滚动优化，可以节省一维的空间，对于python这是巨大的性能提升，cf上有的题二维定义是过不了的。
• 在滚动写法下，完全背包只需在01背包的代码上修改j的转移顺序。
• 多重背包比较进阶，但没那么难，除了单调队列优化外几乎可以看做01背包+完全背包的合体。分类讨论即可：
  • 若v*c>=vol，显然可以认为，对于这个包，这个物品是无限的，因为装满包也都用不完这个物品。
  • 否则可以把这c个物品展开，一个一个遍历，跑c次01背包即可。但是复杂度就上升了
  • 于是出现了多重背包的二进制优化和队列优化。其中二进制优化可以看做01背包做法的组合。
• 分组背包和前三个背包联系就不那么紧密，和01背包还是有关系的(所以01背包是所有背包的基础)：
  • 在01背包的基础上，最外层遍历组，每组选一个；那么组内先遍历体积j，每个j再遍历尝试组内的每个道具。
  • 具体看代码和注释。
• 注意多重背包是无法求方案数的，除非同种物品可以区分。这一般会是分组背包。
• 求方案数时，w价值一般是没用的，只需要考虑体积；且f[0][0]=1。
• 接上：多重背包和分组背包的区分，详细看我代码注释。
• 背包问题的话，acwing的前几道题全是模板可以试试。
• 用我的模板可以秒杀这几道题的大部分。

2. 复杂度分析

1. 查询O(1)
2. 更新update，O(nvolc)。

• 背包问题先看容量，如果容量过大考虑能否优化，比如变成>=的问题。
• 如果无法优化，就要考虑不要用背包做了。考虑其他的dp或者记忆化搜索。

3. 常见应用

1. n个物品求方案数、求极值。

4. 常用优化

1. 空间上可以滚动优化，一般用的比较多的是01背包的倒序枚举转移技巧。
2. 多重背包优化是被提及最多的，可以把c那层优化成lg©或者1。但用的比较少。

二、 模板代码

0. 混合背包求最大/最小值模板(0-1/完全/多重)

例题: 7. 混合背包问题

• 使用时建议外部调用三种方法。
• 如果无法直接用考虑外部手写dp，毕竟不是很复杂。
• 注意很多dp不要强行靠背包。

import sys
from collections import dequeRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')class PackMaxMin:"""    背包问题求最大/最小值，复杂度O(体积*物品(种类)数),如果是多重背包，可以优化成O(体积*物品种类数)有两种使用方法：1. 初始化只传入背包容量vol和极值方法merge(如:max)。外部遍历物品，手动调用p.zero_one_pack等方法。见solve1。好处是不用思考怎么创建dp数组，怎么倒序遍历，遍历时的边界问题(如倒序:range(vol,v-1,-1))2. 初始化同时传入对应类型的物品集合，然后调用run()，可以直接转移完成。但是需要在外部组合起需要的物品，比较麻烦。好处是如果外部本身就组合过了，可以直接算，不用外部暴露逻辑。无法处理的问题:1. 求方案数(另写一个模板)2. 求具体方案(还没想好)3. 二维费用背包:一般是f定义成2维，然后倒序枚举j变成倒序枚举j、k即可，但对代码入侵性较强，变化也多，没想好怎么封装，有空可以尝试写一下试试。"""def __init__(self, vol, zero_one=None, multi=None, complete=None, merge=max):self.zero_one = zero_one  # 用于01背包的物品 (v,w):体积，价值self.multi = multi  # 用于多重背包的物品 (v,w,c):体积，价值，数量self.complete = complete  # 用户完全背包的物品 (v,w):体积，价值self.merge = merge  # 取极值的方案数，一般是maxself.vol = vol  # 背包容量，注意计算复杂度时要用到self.f = [0] * (vol + 1)  # f[j]代表体积j时的最优值，如果是求min这里初始值要改成infdef zero_one_pack(self, v, w):"""        01背包，逆序处理即可滚动v:体积, w:价值"""f, merge = self.f, self.mergefor j in range(self.vol, v - 1, -1):f[j] = merge(f[j], f[j - v] + w)def complete_pack(self, v, w):"""        完全背包，正序处理即可滚动v:体积, w:价值"""f, merge = self.f, self.mergefor j in range(v, self.vol + 1):f[j] = merge(f[j], f[j - v] + w)def multi_pack_by_zero_one(self, v, w, c):"""        多重背包转化成01背包，效率最低，但思考方便，一些无脑dp的题可能可以参考到注意和分组背包区分:外层枚举c个物品，内层倒序枚举j。因为每个物品都要尝试放，扫一遍j。注意有时会和分组背包混淆：如题意描述成，第i种物品有c个，可以任选几个，但同种物品不区分。这种情况用多重背包计算就会出现重复方案，实际上考虑分组背包：这组中有c种物品，只能选0/1个。这c种物品分别是1个i，2个i。。c个i。v:体积, w:价值, c:本物品个数"""if v * c >= self.vol:  # 如果数量足够到超过目标体积，那么可以当完全背包做，更快return self.complete_pack(v, w)f, merge = self.f, self.mergefor _ in range(c):  # 直接展开，尝试c次即可for j in range(self.vol, v - 1, -1):f[j] = merge(f[j], f[j - v] + w)def multi_pack_by_binary(self, v, w, c):"""        多重背包的二进制优化，可以把复杂度里的*c变成*lg(c)。原理是：所有数字都可以用1,2,4,8..等2的幂互相加起来，那么把c分解成这些数字分别尝试逆序转移即可，别忘记最后尝试剩余的部分v:体积, w:价值, c:本物品个数"""if v * c >= self.vol:return self.complete_pack(v, w)f, merge = self.f, self.mergek = 1while k < c:for j in range(self.vol, v * k - 1, -1):f[j] = merge(f[j], f[j - v * k] + w * k)c -= kk <<= 1for j in range(self.vol, v * c - 1, -1):f[j] = merge(f[j], f[j - v * c] + w * c)def multi_pack_by_mono_que(self, v, w, c):"""        多重背包的单调队列优化，可以把复杂度里的*c变成*1。原理需要画图展开消项，比较复杂，还不是很懂。v:体积, w:价值, c:本物品个数"""if v * c >= self.vol:return self.complete_pack(v, w)f, merge = self.f, self.mergepre = f[:]for k in range(v):q = deque()for j in range(k, self.vol + 1, v):if q and q[0] < j - c * v:q.popleft()while q and pre[q[-1]] + (j - q[-1]) // v * w <= pre[j]:q.pop()q.append(j)f[j] = pre[q[0]] + (j - q[0]) // v * wdef run(self):"""直接计算这些背包的转移，除了很模板的题不建议使用"""if self.zero_one:for v, w in self.zero_one:self.zero_one_pack(v, w)if self.multi:for v, w, c in self.multi:self.multi_pack_by_mono_que(v, w, c)if self.complete:for v, w in self.complete:self.complete_pack(v, w)return self.f#   1324    ms
def solve():n, vol = RI()pp = PackMaxMin(vol, merge=max)for _ in range(n):v, w, s = RI()if s == 1 or s == -1:pp.zero_one_pack(v, w)elif s == 0:pp.complete_pack(v, w)else:pp.multi_pack_by_mono_que(v, w, s)  # 1324 ms# pp.multi_pack_by_binary(v, w, s)  # 1349 ms# pp.multi_pack_by_zero_one(v, w, s)  # 1353 msprint(max(pp.f))#     1342   ms
def solve1():n, vol = RI()zero_one, multi, complete = [], [], []for _ in range(n):v, w, s = RI()if s == 1 or s == -1:zero_one.append((v, w))elif s == 0:complete.append((v, w))else:multi.append((v, w, s))pp = PackMaxMin(vol, zero_one=zero_one, multi=multi, complete=complete, merge=max)print(max(pp.run()))if __name__ == '__main__':solve()

1. 分组背包求最大/最小值模板

例题: 9. 分组背包问题

• 分组背包和前边三种写一起感觉不太合适，不太可能放一起出题吧。

import sysRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')class GroupedPackMaxMin:"""分组背包求最大/最小值传入多组物品，每组中只能选一个，求极值。转化成01背包考虑，外层枚举体积j，内层尝试这个j选不同物品(注意和多重背包区分)。注意有时会和多重背包混淆：如题意描述成，第i种物品有c个，可以任选几个，但同种物品不区分。这种情况用多重背包计算就会出现重复方案，实际上考虑分组背包：这组中有c种物品，只能选0/1个。这c种物品分别是1个i，2个i。。c个i。"""def __init__(self, vol, grouped_items=None, merge=max):self.grouped_items = grouped_items  # 形如[[(1,2),(2,3)],[(1,2),(2,3)],]，注意是多组数组，每组中只能选一个self.merge = mergeself.vol = volself.f = [0] * (vol + 1)  # f[j]代表体积j时的最优值，如果是求min这里初始值要改成infdef grouped_pack(self, items):f, merge = self.f, self.mergefor j in range(self.vol, 0, -1):for v, w in items:if j >= v:f[j] = merge(f[j], f[j - v] + w)def run(self):if self.grouped_items:for items in self.grouped_items:self.grouped_pack(items)return self.f#    1065   ms
def solve():n, vol = RI()gp = GroupedPackMaxMin(vol)for _ in range(n):s, = RI()a = []for _ in range(s):a.append(RILST())gp.grouped_pack(a)print(max(gp.f))#    1071    ms
def solve1():n, vol = RI()items = []for _ in range(n):s, = RI()a = []for _ in range(s):a.append(RILST())items.append(a)gp = GroupedPackMaxMin(vol, items)print(max(gp.run()))if __name__ == '__main__':solve()

2. 01背包求方案数模板(完全背包也在，但没测)

例题: 11. 背包问题求方案数

• 这题本质是01背包求方案数。但题目问题的是最大价值的方案数，因此要先计算最大价值，看什么体积是最大价值，然后再根据体积算。因此代码多一点。

import sysRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')MOD = 10 ** 9 + 7class PackMaxMin:"""    背包问题求最大/最小值，复杂度O(体积*物品(种类)数),如果是多重背包，可以优化成O(体积*物品种类数)有两种使用方法：1. 初始化只传入背包容量vol和极值方法merge(如:max)。外部遍历物品，手动调用p.zero_one_pack等方法。见solve1。好处是不用思考怎么创建dp数组，怎么倒序遍历，遍历时的边界问题(如倒序:range(vol,v-1,-1))2. 初始化同时传入对应类型的物品集合，然后调用run()，可以直接转移完成。但是需要在外部组合起需要的物品，比较麻烦。好处是如果外部本身就组合过了，可以直接算，不用外部暴露逻辑。无法处理的问题:1. 求方案数(另写一个模板)2. 求具体方案(还没想好)3. 二维费用背包:一般是f定义成2维，然后倒序枚举j变成倒序枚举j、k即可，但对代码入侵性较强，变化也多，没想好怎么封装，有空可以尝试写一下试试。"""def __init__(self, vol, zero_one=None, multi=None, complete=None, merge=max):self.zero_one = zero_one  # 用于01背包的物品 (v,w):体积，价值self.multi = multi  # 用于多重背包的物品 (v,w,c):体积，价值，数量self.complete = complete  # 用户完全背包的物品 (v,w):体积，价值self.merge = merge  # 取极值的方案数，一般是maxself.vol = vol  # 背包容量，注意计算复杂度时要用到self.f = [0] * (vol + 1)  # f[j]代表体积j时的最优值，如果是求min这里初始值要改成infdef zero_one_pack(self, v, w):"""        01背包，逆序处理即可滚动v:体积, w:价值"""f, merge = self.f, self.mergefor j in range(self.vol, v - 1, -1):f[j] = merge(f[j], f[j - v] + w)def complete_pack(self, v, w):"""        完全背包，正序处理即可滚动v:体积, w:价值"""f, merge = self.f, self.mergefor j in range(v, self.vol + 1):f[j] = merge(f[j], f[j - v] + w)def multi_pack_by_zero_one(self, v, w, c):"""        多重背包转化成01背包，效率最低，但思考方便，一些无脑dp的题可能可以参考到注意和分组背包区分:外层枚举c个物品，内层倒序枚举j。因为每个物品都要尝试放，扫一遍j。注意有时会和分组背包混淆：如题意描述成，第i种物品有c个，可以任选几个，但同种物品不区分。这种情况用多重背包计算就会出现重复方案，实际上考虑分组背包：这组中有c种物品，只能选0/1个。这c种物品分别是1个i，2个i。。c个i。v:体积, w:价值, c:本物品个数"""if v * c >= self.vol:  # 如果数量足够到超过目标体积，那么可以当完全背包做，更快return self.complete_pack(v, w)f, merge = self.f, self.mergefor _ in range(c):  # 直接展开，尝试c次即可for j in range(self.vol, v - 1, -1):f[j] = merge(f[j], f[j - v] + w)def multi_pack_by_binary(self, v, w, c):"""        多重背包的二进制优化，可以把复杂度里的*c变成*lg(c)。原理是：所有数字都可以用1,2,4,8..等2的幂互相加起来，那么把c分解成这些数字分别尝试逆序转移即可，别忘记最后尝试剩余的部分v:体积, w:价值, c:本物品个数"""if v * c >= self.vol:return self.complete_pack(v, w)f, merge = self.f, self.mergek = 1while k < c:for j in range(self.vol, v * k - 1, -1):f[j] = merge(f[j], f[j - v * k] + w * k)c -= kk <<= 1for j in range(self.vol, v * c - 1, -1):f[j] = merge(f[j], f[j - v * c] + w * c)def multi_pack_by_mono_que(self, v, w, c):"""        多重背包的单调队列优化，可以把复杂度里的*c变成*1。原理需要画图展开消项，比较复杂，还不是很懂。v:体积, w:价值, c:本物品个数"""if v * c >= self.vol:return self.complete_pack(v, w)f, merge = self.f, self.mergepre = f[:]for k in range(v):q = deque()for j in range(k, self.vol + 1, v):if q and q[0] < j - c * v:q.popleft()while q and pre[q[-1]] + (j - q[-1]) // v * w <= pre[j]:q.pop()q.append(j)f[j] = pre[q[0]] + (j - q[0]) // v * wdef run(self):"""直接计算这些背包的转移，除了很模板的题不建议使用"""if self.zero_one:for v, w in self.zero_one:self.zero_one_pack(v, w)if self.multi:for v, w, c in self.multi:self.multi_pack_by_mono_que(v, w, c)if self.complete:for v, w in self.complete:self.complete_pack(v, w)return self.fclass PackCountPlan:"""    背包问题求方案数，复杂度O(体积*物品(种类)数),一般求方案数很大，都要取模，这里为了防止忘记取模/模写错，直接调用全局变量，如果忘记定义会报错。注意和求极值不同：1. dp[0][0] = 1代表 一个不取的方案数是12. 数组里只需要一列体积参数，不需要价值。一般是01背包，完全背包。可能无法处理多重背包，因为无法区分同种类物品。这时尝试考虑分组背包，把每种物品看成一组，这组里的物品分别是1个i,2个i..c个i。"""def __init__(self, vol, zero_one=None, multi=None, complete=None):self.zero_one = zero_one  # 用于01背包的物品 (v):体积self.multi = multi  # 用于多重背包的物品 (v,c):体积，数量--- 注意用不了，我只是没删，可能后续想办法补。self.complete = complete  # 用户完全背包的物品 (v):体积self.vol = vol  # 背包容量，注意计算复杂度时要用到self.f = [1] + [0] * vol  # f[j]代表体积j时的方案，如果是求min这里初始值要改成infdef zero_one_pack(self, v):"""        01背包，逆序处理即可滚动v:体积"""f = self.ffor j in range(self.vol, v - 1, -1):f[j] = (f[j] + f[j - v]) % MODdef complete_pack(self, v, w):"""        完全背包，正序处理即可滚动v:体积, w:价值"""f = self.ffor j in range(v, self.vol + 1):f[j] = (f[j] + f[j - v]) % MODdef run(self):"""直接计算这些背包的转移，除了很模板的题不建议使用"""if self.zero_one:for v in self.zero_one:self.zero_one_pack(v)if self.complete:for v in self.complete:self.complete_pack(v)return self.f#       ms
def solve():n, vol = RI()a = []for _ in range(n):a.append(RILST())# 先求最大价值pm = PackMaxMin(vol, a)f = pm.run()mx = max(f)js = [j for j, v in enumerate(f) if v == mx]# 以下是求方案数部分pc = PackCountPlan(vol)for v, _ in a:pc.zero_one_pack(v)print(sum(pc.f[j] for j in js))if __name__ == '__main__':solve()

3. 分组背包求方案数

例题: 6310. 获得分数的方法数

• 比赛前没学过分组背包，赛中一直以为是多重背包，结果不会去重，做不出来。
• 这里整理成模板。
• 本题注意是分组背包，因为同一种物品无法区分，相当于每种物品是一组，组内可以选任意一种物品(k个物品的组合。)

MOD = 10**9+7class GroupedPackCountPlan:"""    分组背包问题求方案数，复杂度O(体积*物品(种类)数),一般求方案数很大，都要取模，这里为了防止忘记取模/模写错，直接调用全局变量，如果忘记定义会报错。注意和求极值不同：1. dp[0][0] = 1代表 一个不取的方案数是12. 数组里只需要一列体积参数，不需要价值。一般是01背包，完全背包。可能无法处理多重背包，因为无法区分同种类物品。这时尝试考虑分组背包，把每种物品看成一组，这组里的物品分别是1个i,2个i..c个i。"""def __init__(self, vol, grouped_items=None):self.grouped_items = grouped_items  # 用于01背包的物品 (v):体积        self.vol = vol  # 背包容量，注意计算复杂度时要用到self.f = [1] + [0] * vol  # f[j]代表体积j时的方案，如果是求min这里初始值要改成infdef grouped_pack(self, items):  # 注意传进来的是本组的物品的体积们:[1,6,2,3,4,5..]，最好是排序的可以优化一下breakf = self.ffor j in range(self.vol, 0, -1):  # 注意外层循环遍历体积j，内层尝试放组内每个物品。for v in items:if j >= v:  # 这里可以尝试sort break，但是最好能在外层预处理或者天然是排序的。f[j] = (f[j]+f[j - v] )%MOD   def run(self):"""直接计算这些背包的转移，除了很模板的题不建议使用"""if self.grouped_items:for v in self.grouped_items:self.grouped_pack(items)   return self.fclass Solution:def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:                     gp = GroupedPackCountPlan(target)for count,marks in types:items = []  # 本组物品的体积相当于尝试用k个marks，其中k<=countfor i in range(1,count+1):items.append(marks*i)gp.grouped_pack(items)  # 整理好本组物品再一起传进去             return gp.f[-1] % MOD

6. 转化为01背包

例题: LCP 47. 入场安检

• 如果有x个房间，他们都转为栈模式，那么只要他们先进去共k个人，且每个房间都剩个尾巴，那所有房间就都变成了队列，第k个人就正好可以第一个出来了。
• 因此转化为01背包，容量是k，物品是房间，价值是1，体积是cap[i]-1。问多少种组合能满足体积是k。

class Solution:def securityCheck(self, capacities: List[int], k: int) -> int:MOD = 1000000007 n = len(capacities)# m = len(capacities[-1])# 房间是物品，k是容量f = [0]*(k+1)f[0] = 1for v in capacities:v -= 1for j in range(k,v-1,-1):f[j] = (f[j]+f[j-v])%MODreturn f[-1]

三、其他

1. 多重背包的单调队列优化暂时不会，先复制。
2. 二维费用背包的后续在写。

四、更多例题

五、参考链接