@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+4
volume = 10
dp = [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

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

Runsen接着看原题，输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

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

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。具体连接如下：https://www.acwing.com/problem/content/description/5/

'''
@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 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卡了几天。 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 5
1 2 3
2 4 1
3 4 3
4 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

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

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

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/108644080