本文共 2996 字，大约阅读时间需要 9 分钟。

@Author：Runsen

@Date：2020/9/17

多重背包有三层循环，如果数据非常的大，那么程序就会变得非常悲伤。在多重背包的问题，其实更多的是考查多重背包的二进制优化方法。学习二进制优化方法，对下面的混合背包才能开始。所以一步扣一步的。

二进制优化方法

这个时候我们就需要优化，有一种优化方式叫做二进制优化

二进制是一个非常神奇的进制，譬如说7这个数，分开就是$1+2+4（2^0+2^1+2^2）$。

进行完二进制拆分之后，这个问题就转化成了零一背包。

下面就是一个二进制解决多重背包的示例，其中items 表示次数，体积 价值。

'''@Author： Runsen@WeChat：RunsenLiu @微信公众号： Python之王@CSDN： https://blog.csdn.net/weixin_44510615@Github： https://github.com/MaoliRUNsen@Date： 2020/9/17'''def binary_divide(cnt, volume, price):    divides = []    for i in range(32):        # 从0位开始枚举        cur = 1 << i        # 如果小于枚举值，说明已经拆分完毕了        if cnt < cur:            # 把剩下的部分打包            divides.append((cnt, cnt * volume, cnt * price))            break        else:            # 否则继续拆分，打包1 << i个物品            cnt -= cur            divides.append((cur, cur * volume, cur * price))    return divides# cnt, volume, price 次数，体积 价值items = [[3, 3, 5], [4, 2, 3], [1, 2, 4]]  #17= 5+3+5+4volume = 10dp = [0  for _ in range(volume+1)]new_items = []for i in items:    # 二进制拆分    print(*i)  # [1, 2, 4]=> 1,2,4      new_items.extend(binary_divide(*i))print(new_items)# 零一背包for item in new_items:    v, p = item[1], item[2]    for i in range(volume-v, -1, -1):        dp[i + v] = max(dp[i+v], dp[i] + p)print(dp[-1])[(1, 3, 5), (2, 6, 10), (0, 0, 0), (1, 2, 3), (2, 4, 6), (1, 2, 3), (1, 2, 4), (0, 0, 0)]17

Runsen接着看原题，输入格式

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

数据范围

'''@Author： Runsen@WeChat：RunsenLiu @微信公众号： Python之王@CSDN： https://blog.csdn.net/weixin_44510615@Github： https://github.com/MaoliRUNsen@Date： 2020/9/21'''def binary_divide(volume,price,count):    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 dividesn,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卡了几天。    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])4 51 2 32 4 13 4 34 5 2[(1, 1, 2), (2, 2, 4), (0, 0, 0), (1, 2, 4), (0, 0, 0), (1, 3, 4), (2, 6, 8), (0, 0, 0), (1, 4, 5), (1, 4, 5)]10

在这里需要区别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)]

转载地址：https://maoli.blog.csdn.net/article/details/108644080 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！