当前位置：首页 > news >正文

算法第十五期——动态规划(DP)之各种背包问题

news 文章来源：https://blog.csdn.net/m0_69478345/article/details/128715055 2025/1/10 17:07:52

0、背包问题分类

1、 0/1背包简化版

【代码】

2、0/ 1背包的方案数

【思路】

【做法】

【代码】

空间优化1：交替滚动

空间优化2：自我滚动

3、完全背包

【思路】

【代码】

4、分组背包

核心代码

5、多重背包

多重背包解题思路1:转化为0/1背包

多重背包解题思路2:直接DP

核心代码

多重背包解题思路3:二进制拆分优化

拆分要点

多重背包解题思路4:单调队列

模板题

【代码】

0、背包问题分类

背包问题可分为0/1背包简化版，背包方案数，完全背包，分组背包，多重背包等

1、 0/1背包简化版

0/1背包的简化版：不管物品的价值。把体积看成最优化目标：最大化体积。

装箱问题 lanqi ao0J题号763

题目描述

有一个箱子容量为 V（正整数，0≤V≤20000），同时有 n 个物品（0≤n≤30），每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述

输入第一行，一个整数，表示箱子容量。

第二行，一个整数 n，表示有 n 个物品。

接下来 n 行，分别表示这 n 个物品的各自体积。

输出描述

输出一行，表示箱子剩余空间。

输入输出样例

输入
24
6
8
3
12
7
9
7
输出
0

0/1背包的简化版，不管物品的价格。把体积（不是价格）看成最优化目标:最大化体积。

【代码】

dp = [0]*20010
V = int(input())# 容量
n = int(input())# 物品数
c = [0]*40      # 存每个物品体积
# 读入每个物体的体积
for i in range(1, n+1): c[i]=int(input ())
# 自我滚动
for i in range (1, n+1) :for j in range (V, c[i]-1,-1):dp[j] = max(dp[j],dp[j-c[i]]+c[i])
print(V-dp[V]) # 剩余最小容量 = 容量 - 物品最大体积

2、0/ 1背包的方案数

2022年届国赛，填空题，langiao0J题号2186

问题描述

将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法?

注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 2022=1022+1000 就视为同一种方法。

答案提交

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

【思路】

题目求10个数的组合情况，这十个数相加等于2022。因为是填空题可以不管运行时间，看起来可以用暴力for循环10次，加上剪枝。然而暴力的时间极长，因为答案是:379187662194355221。
建模：这一题其实是0/1背包：背包容量为2022，物品体积为1~2022，往背包中装10个物品，要求总体积为2022，问一共有多少种方案。
与标准背包的区别:是求方案总数。

【做法】

定义dp[ ][ ][ ]: dp[i][i][k]表示数字1~i取j个，容量为k的方案数。
下面的分析沿用标准0/1背包的分析方法。
从i-1扩展到i，分两种情况:

(1) k>i：数i可以要，也可以不要。
要i： 从1~i-1中取j-1个数，再取i，等价于dp[i-1][j-1][k-i]。

不要i：从1~i-1中取j个数，等价于dp[i-1][i][k]
合起来（要和不要的总方案数）: dp[i][i][k] = dp[i-1][i][k] + dp[i-1][j-1][k-i]
( 2) k<i：由于数i比总和k还大，显然i不能用。有: dp[i][i][k]= dp[i-1][ji][k]

【代码】

空间优化1：交替滚动

dp = [[[0]*2222 for i in range(11)] for j in range(2222)]   # 比题目要求的数据范围大一点
for i in range(0,2023): dp[i][0][0]=1 # 初始化：递推条件的初始值，不选也是一种方案
for i in range(1,2023):for j in range(1,11):for k in range(1,2023):if k<i: dp[i][j][k] = dp[i-1][j][k]else:dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-i]
print(dp[2022][10][2022])

空间优化2：自我滚动

dp = [[0]*2222 for i in range(11)]
dp[0][0] = 1    #特别注意这个初始化
for i in range(1,2023):for j in range (10,0,-1):    # 10个数for k in range(i,2023):  # k>=idp[j][k] += dp[j-1][k-i]
print(dp[10][2022])

3、完全背包

特点：每种物品有无穷多个

小明的背包2lanqiao0J题号1175

题目描述

小明有一个容量为 V 的背包。

这天他去商场购物，商场一共有 N 种物品，第 i 种物品的体积为 wi，价值为 vi，每种物品都有无限多个。

小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。

第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。

1≤N≤10^3，1≤V≤10^3，1≤wi,vi≤10^3。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

输入
5 20
1 6
2 5
3 8
5 15
3 3 
输出
120

【思路】

和0/1背包类似。0/1背包的每种物品只有1件，完全背包的每种物品有无穷多件，第i种可以装0件、1件、2件、.....、 $C//c_i$ 件。
做法：定义dp[i][j]：把前i种物品（从第1种到第i种）装入容量为j的背包中获得的最大价值。把每个dp[i][j]都看成一个背包：背包容量为j，装1~i这些物品。最后得到的dp[N][C]就是问题的答案:把N种物品装进容量C的背包的最大价值。
区别：在0/1背包问题中，每个物品只有拿与不拿两种;而完全背包问题，需要考虑拿几个

【代码】

完全背包的代码和0/1背包的代码相似，只多了一个k循环，用来遍历每种物品拿几个。

def solve(n,C) :for i in range (1, n+1):for j in range (0,C+1):dp[i][j] = dp[i - 1][j]      # 初始化为都不装的情况for k in range(1,j//c[i]+1): # 可以拿1~j//c[i]个该物品  k*c[i]<=j #在容量为j的背包中放k个dp[i][j] = max(dp[i][j],dp[i - 1][j - k * c[i]] +k * w[i])return dp[n][C]N = 3011
dp = [[0]*N for j in range(N)]
w =[0]*N; c = [0]*N
n,C = map(int,input().split())
for i in range(1, n+1):c[i], w[i] = map(int,input ().split())  # 每个物品的体积和价值
print(solve(n,C))

也可以不需要初始化条件，但下面要从0个该物品开始遍历，这样写代码更加简洁，但时间复杂度高了一点，代码如下：

def solve(n,C) :for i in range (1, n+1):for j in range (0,C+1):dp[i][j] = dp[i - 1][j]      # 初始化为都不装的情况for k in range(1,j//c[i]+1): # 可以拿1~j//c[i]个该物品  k*c[i]<=j #在容量为j的背包中放k个dp[i][j] = max(dp[i][j],dp[i - 1][j - k * c[i]] +k * w[i])return dp[n][C]N = 3011
dp = [[0]*N for j in range(N)]
w =[0]*N; c = [0]*N
n,C = map(int,input().split())
for i in range(1, n+1):c[i], w[i] = map(int,input ().split())  # 每个物品的体积和价值
print(solve(n,C))

4、分组背包

分组背包问题:

有一些物品，把物品分为n组，其中第i组第k个物品体积是c[i][k]，价值是w[i][k];
每组内的物品冲突，每组内最多只能选出一个物品;
给定一个容量为C的背包，问如何选物品，使得装进背包的物品的总价值最大。

解题思路与0/1背包相似。

0/1背包dp[i][j]：把前i个物品（从第1个到第i个）装入容量为j的背包中获得的最大价值。
分组背包dp[i][j]：把前i组物品装进容量j的背包（每组最多选一个物品)，可获得的最大价值。
状态转移方程：
dp[i][j] = max {dp[i-1][j]，dp[i-1][j-c[i][k]] + w[i][k]} dp[i-1][j]表示第i组不选物品，dp[i-1][j-c[i][k]]表示第i组选第k个物品。
求解方程需要做i、j、k的三重循环。

核心代码：

状态转移方程:dp[i][j] = max {dp[i-1][j], dp[i-1][j-c[i][k]] + w[i][k]}，用滚动数组，变为:dp[j] = max {dp[j]，dp[j-c[i][k]]+ w[i][k]}

dp = [0] * N
for i in range(1, n + 1):       # 遍历每个组for j in range(C, -1, -1):  # 枚举容量for k in range(1, C + 1):  # 用k枚举第i组的所有物品if j >= c[i][k]:       # 第k个物品能装进容量j的背包dp[j] = max(dp[j], dp[j - c[i][k]] + w[i][k])  # 第i组第k个
print(dp[C])

5、多重背包

多重背包问题:

给定n种物品和一个背包，第i种物品的体积是ci，价值为wi，并且有mi个，背包的总容量为C。
如何选择装入背包的物品，使得装入背包中的物品的总价值最大?
与完全背包的区别：完全背包是每种物品都有无限多个，而多重背包是有限个

多重背包解题思路1:转化为0/1背包

转换为0/1背包问题。
把相同的 $m_i$ 个第i种物品看成独立的 $m_i$ 个，总共 $\sum_{i=1}^{n}m_i$ 个物品，。
然后按0/1背包求解，复杂度 $O(C*\sum_{i=1}^{n}m_i)$ 。

多重背包解题思路2:直接DP

定义状态dpli][j]:表示把前i个物品装进容量j的背包，能装进背包的最大价值。
第i个物品分为装或不装两种情况，状态转移方程:

dp[i][j] = max {dp[i-1][j]，dp[i-1][j-k*c[i]] ＋k*w[i]}
1 ≤k ≤min{m[i], j/c[i]} # k不能超过 $m_i$ 个和最大容量个数的最小值

直接写i、j、k三重循环，复杂度和第一种思路的复杂度一样。
对比完全背包:1≤k ≤ j/c[i]

核心代码：

状态转移方程:dp[i][j] = max {dp[i-1][j], dp[i-1][j-k*c[i]]+ k*w[i]}，用滚动数组，变为:dp[j] = max{dp[j]，dp[j-k*c[i]]＋ k*w[i]}。

dp = [0]*N
for i in range(1, n+1):           #枚举物品for j in range (C,c[i]-1,-1): #枚举背包容量for k in range(1,m[i]+1):     #用k遍历第i组的所有物品if(j >= k*c[i]):          #第k个物品能装进容量j的背包dp[j] = max(dp[j], dp[j-k*c[i]]+k*w[i])
print(dp[C])

多重背包解题思路3:二进制拆分优化

一种简单而有效的技巧。
例如第i种物品有 $m_i$ = 25个，这25个物品放进背包的组合，有0~25的26种情况。
不过要组合成26种情况，其实并不需要25个物品。
根据二进制的计算原理，一个十进制整数X，可以用1、2、4、8、...这些2的倍数相加得到，例如25=16+8+1，这些2的倍数只有logX个。
题目中第i种物品有 $m_i$ 个，用log $m_i$ 个数就能组合出0 ~ $m_i$ 种情况。总复杂度从 $O(C*\sum_{i=1}^{n})$ 优化到 $O(C*\sum_{i=1}^{n}log_2m_i)$ 。

拆分要点：

注意拆分的具体实现，不能全部拆成2的倍数，而是先按2的倍数从小到大拆，最后是一个小于等于最大倍数的余数。
保证拆出的数相加在[1, mi]范围内，不会大于mi。
例如mi= 25，把它拆成1、2、4、8、10，最后是余数10，10<16，这5个数能组合成1~25内的所有数字，不会超过25。
错误示例：如果把25拆成1、2、4、8、16，相加的范围就是[1,31]了。

多重背包解题思路4:单调队列

因为这一讲主要是讲dp算法，所以就不在直接过多介绍其他算法，但这个方法优化程度更高，有兴趣的朋友可以看看这篇文章：单调队列优化多重背包（全网最详细解析）

模板题

【输入描述】第一行是整数n和C，分别表示物品种数和背包的最大容量。接下来 n行，每行三个整数 wi、ci、mi，分别表示第i个物品的价值、体积、数量。
【输出描述】输出一个整数，表示背包不超载的情况下装入物品的最大价值。
【输入样例】

4 20

3 9 3

5 9 1

9 4 2

8 1 3

【输出样例】

【代码】

代码用二进制拆分优化来解答。

N = 100010
w = [0] * N;c = [0] * N;m = [0] * N
xw = [0] * N;xc = [0] * N   # 经过二进制拆分后的新体积和新价值，转换后每个物体只有一个，所以没有新的数量n, C = map(int, input().split())
for i in range(1, n + 1):w[i], c[i], m[i] = map(int, input().split())# 以下是二进制拆分
xn = 0  # 二进制拆分后的新物品总数量
for i in range(1, n + 1):j = 1while j <= m[i]:  # 例:直到最后一个数m[i]（余数）出现m[i] -= j     # 减去已拆分的xn += 1xc[xn] = j * c[i]  # 新物品的体积xw[xn] = j * w[i]j <<= 1       # 二进制枚举:1,2,4...if m[i] > 0:      # 最后一个是余数xn += 1xc[xn] = m[i] * c[i]xw[xn] = m[i] * w[i]
# 以下是滚动数组版本的0/1背包
dp = [0] * N
for i in range(1, xn + 1):  # 枚举物品for j in range(C, xc[i] - 1, -1):  # 枚举背包容量  xc[i] - 1这里的-1是因为range函数是左闭右开区间，-1才能取到xc[i]dp[j] = max(dp[j], dp[j - xc[i]] + xw[i])
print(dp[C])

$O(C*\sum_{i=1}^{n}log_2m_i)$

0、背包问题分类

1、 0/1背包简化版

题目描述

输入描述

输出描述

输入输出样例

【代码】

2、0/ 1背包的方案数

问题描述

答案提交

【思路】

【做法】

【代码】

空间优化1：交替滚动

空间优化2：自我滚动

3、完全背包

题目描述

输入描述

输出描述

输入输出样例

【思路】

【代码】

4、分组背包

核心代码：

5、多重背包

多重背包解题思路1:转化为0/1背包

多重背包解题思路2:直接DP

核心代码：

多重背包解题思路3:二进制拆分优化

拆分要点：

多重背包解题思路4:单调队列

模板题

【代码】

相关文章：