九十一、动态规划系列背包问题之混合背包
Python之王
共 12306字，需浏览 25分钟
·
2021-03-20 16:52
「@Author：Runsen」
背包系列，是动态规划里一类典型的问题，主要有：01背包，完全背包，多重背包，混合背包，二维费用背包，分组背包，有依赖背包和泛化物品等。也就是常说的背包九讲。
前面说了01背包问题，完全背包问题，多重背包问题，其主要是每件物品可选个数有区别。
混合背包是有N种物品和一个容量为V的背包。有的物品只可以取一次(01背包)，有的物品可以取无限次(完全背包)，有的物品可以取的次数有一个
混合背包
今天学习的混合背包问题混合了这三者。
题目是这样的，来源：https://www.acwing.com/problem/content/7/
# -1 表示01背包 0表示完全背包 大于0的表示多重背包
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
最简单的方法就是直接转化为多重背包。-1变成1，0变成V，这样就是最简单最高效的方法。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/9/27
# -1 表示01背包 0表示完全背包 大于0的表示多重背包
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
'''
n, v = map(int, input().split())
dp = [0 for _ in range(v+1)]
for i in range(n):
b, w, s = map(int, input().split())
# 这里需要判断下s
if s == -1 : s = 1
if s == 0 : s = v
for j in range(v, -1, -1):
k = 1
while k <= s and j >= k * b:
dp [j] = max(dp [j], dp [j - k*b] + k*w)
k += 1
print(dp[v])
上次我用了二进制的方法进行了优化，混合背包当然也可以转为多重背包的二进制的方法。具体代码如下所示。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/9/27
二进制优化方法
# -1 表示01背包 0表示完全背包 大于0的表示多重背包
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
'''
def binary_divide(volume,price,count):
# 这里需要多count进行改正
if count == -1 :count = 1
if count == 0: count = v
divides = []
for i in range(32):
# 从0位开始枚举
cur = 1 << i
# 如果小于枚举值，说明已经拆分完毕了
if count < cur:
# 把剩下的部分打包
divides.append((count, count * volume, count * price))
break
else:
# 否则继续拆分，打包1 << i个物品
count -= cur
divides.append((cur, cur * volume, cur * price))
return divides
n,v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
new_good = []
for i in goods:
# 二进制拆分 这里需要区别extend和append的用法
'''
>>> s = []
>>> s.extend([(1, 1, 2), (2, 2, 4), (0, 0, 0)])
>>> s
[(1, 1, 2), (2, 2, 4), (0, 0, 0)]
>>> s[0]
(1, 1, 2)
>>> a = []
>>> a.append([(1, 1, 2), (2, 2, 4), (0, 0, 0)])
>>> a
[[(1, 1, 2), (2, 2, 4), (0, 0, 0)]]
>>> a[0]
[(1, 1, 2), (2, 2, 4), (0, 0, 0)]
'''
new_good.extend(binary_divide(*i))
dp = [0 for _ in range(v+1)]
for item in new_good:
i, j = item[1], item[2]
for k in range(v - i, -1, -1):
dp[k + i] = max(dp[k + i], dp[k] + j)
print(dp[-1])
九月，我等下一个秋天，也等下一个你。
二维费用的背包问题
二维费用的背包问题。直接让我想起了Vivo的面试题，具体链接
输入
15 10 5,1,1000#2,3,3000#5,2,15000#10,4,16000
输出
31000
说明
组合部署服务5,2,15000、10,4,16000 ，可以让单台服务器承载最大用户数31000
那时候的我不会做，现在的我实力有一点滴提高，看看可以A掉不？「这必须A掉」！在vivo这题就是少了一个服务器的个数。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/9/27
输入：15 10 5,1,1000#2,3,3000#5,2,15000#10,4,16000
输出：31000
考点：动态规划
'''
'''
Welcome to vivo !
'''
def solution(total_disk, total_memory, app_list):
# 背包的二维费用问题 三维dp解决
disk_sum = []
memory_sum = []
apps = []
for i in app_list:
disk_sum.append(i[0])
memory_sum.append(i[1])
apps.append(i[2])
n = len(apps)
# 状态 三维dp dp[i][j][k] 表示第i个服务器，磁盘空间为j，内存为k的最大APP部署应用的个数
# dp[i][j][k] 要么就是第i-1个服务器，磁盘空间为j，内存为k的最大APP部署应用的个数，
# 要么就是第i-1个服务器，磁盘空间为j-（i-1）的空间，内存为k-（i-1）的空间的最大APP部署应用的个数（需要判断当前j和k能不能大于i-1的状态
# 这里需要注意：为什么dp定义成n+1？
dp = [[[0] * (total_memory + 1) for _ in range(total_disk + 1)] for _ in range(n + 1)]
# 因为最后的一个n+1，需要取到n
for i in range(1, n + 1):
for j in range(1, 1 + total_disk):
for k in range(1, 1 + total_memory):
# 需要判断当前j和k能不能大于i-1的状态
if j - disk_sum[i - 1] >= 0 and k - memory_sum[i - 1] >= 0:
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - disk_sum[i - 1]][k - memory_sum[i - 1]] + apps[i - 1])
else:
# 判罚失败，只有一种来源
dp[i][j][k] = dp[i-1][j][k]
return dp[-1][-1][-1]
if __name__ == "__main__":
# 15 10 5,1,1000#2,3,3000#5,2,15000#10,4,16000
input1 = input()
disk = int(input1.split()[0])
memory = int(input1.split()[1])
input2 = input1.split()[2]
app_list = [[int(j) for j in i.split(',')] for i in input2.split('#')]
print(solution(disk, memory, app_list))
# 顺便更新将三维空间压缩成二维空间的超级简单的做法
input1 = input()
A = int(input1.split()[0])
B = int(input1.split()[1])
input2 = input1.split()[2]
app_list = [[int(j) for j in i.split(',')] for i in input2.split('#')]
dp = [[0 for _ in range(B+1)] for _ in range(A+1)]
for a,b,c in app_list:
for j in range(A, a - 1, -1):
for k in range(B, b - 1, -1):
dp[j][k] = max(dp[j][k], dp[j - a][k - b] + c)
print(dp[-1][-1])
15 10 5,1,1000#2,3,3000#5,2,15000#10,4,16000
31000
我重新来看二维费用的背包问题
只要知道了三维的dp的状态转移方程：dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-V[i-1]][k-M[i-1]]+W[i-1])。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/9/27
'''
n,v,m = map(int,input().split())
dp = [[[0] * (m+1) for _ in range(v+1)] for _ in range(n+1)]
V = []
M = []
W = []
for i in range(n):
# 体积、重量和价值
a,b,c = map(int,input().split())
V.append(a)
M.append(b)
W.append(c)
for i in range(1,n+1):
# j是容量
for j in range(1,v+1):
# k是重量
for k in range(1,m+1):
if j-V[i-1] >= 0 and k-M[i-1] >= 0:
dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-V[i-1]][k-M[i-1]]+W[i-1])
else:
dp[i][j][k] = dp[i-1][j][k]
print(dp[-1][-1][-1])
下面教大家一个通神的方法，叫做逆序，可以将三维dp直接进行空间优化成二维dp，其原理就是斐波那契数列的从底向顶的做法，逆向思维。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/9/27
'''
n,v,m = map(int,input().split())
dp = [[0 for _ in range(m+1)] for _ in range(v+1)]
for i in range(n):
# 体积、重量和价值
a, b, c = map(int, input().split())
for j in range(v, a - 1, -1):
for k in range(m, b - 1, -1):
dp[j][k] = max(dp[j][k], dp[j - a][k - b] + c)
print(dp[-1][-1])
背包系列还有，分组背包，有依赖背包和泛化物品（方案数），在此个人觉得没有必要了，掌握零一背包、多重背包、完全背包和混合背包已经很不错了。
更多的文章
点击下面小程序
- END -
评论