九十一、动态规划系列背包问题之混合背包

共 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 -


浏览 49
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报