空间优化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件、.....、件。
做法：定义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背包问题。
• 把相同的个第i种物品看成独立的个，总共个物品，。
• 然后按0/1背包求解，复杂度。

多重背包解题思路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不能超过 个和最大容量个数的最小值

• 直接写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种物品有= 25个，这25个物品放进背包的组合，有0~25的26种情况。
• 不过要组合成26种情况，其实并不需要25个物品。
• 根据二进制的计算原理，一个十进制整数X，可以用1、2、4、8、...这些2的倍数相加得到，例如25=16+8+1，这些2的倍数只有logX个。
• 题目中第i种物品有个，用log个数就能组合出0 ~种情况。总复杂度从优化到。

拆分要点：

• 注意拆分的具体实现，不能全部拆成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

【输出样例】

47

【代码】

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

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])