# 多重背包 今天蛋糕店的活动已经结束了，开始了正常的营业。于是我们又遇到了新问题。 蛋糕店现出售`n`种蛋糕🎂，每种蛋糕都有三种属性`cost[i]`，`val[i]`，`num[i]`，分别表示第`i`种蛋糕的`单价`，`喜爱值`，`数量`。我现在只有`v`元钱，我希望能够买到的蛋糕的`总喜爱值`尽可能的大，那么我应该怎么样购买呢？ ## 分析 ### 解法1 很容易想到一种非常`暴力`的解法，将每种蛋糕都拆分成`num[i]`个，然后当成01背包来做就好了，不过当`num[i]`过大时，拆分物品的数量太多，会花费太长的时间。 ### 解法2 可以使用如下方法来减少拆分的数量： >考虑十进制下(15)可以表示成二进制下的(1111)，那么如果把15拆成(1000)，(0100)，(0010)，(0001)，也就是`1，2，4，8`这样就可以表示15一下的所有整数了。 对于某些二进制形式不全为1的数字，比如14(1110)，应该从`1，2，4，8，...`的顺序来拆分，最后剩余的部分直接保留，也就是拆分成`1，2，4，7`，而不是拆成`1，4，8`。 用这种二进制拆分法来拆分每种物品，每种物品最后会被拆分成`log2(num[i])`个左右，一般来说如果`num[i]<1e9`，那么就是`20~30`个，这是可以接受的。拆分后按照01背包的解法就可以解决这个问题了。 ### 二进制拆分复杂度及代码 时间复杂度：O(log2(n)) 空间复杂度：O(log2(n)) 代码： ~~~py n = int(input()) res = [] # 拆分结果 m = 100 # log2(MAX_N) for i in range(m): if n>(1<<i): res.append(1<<i) n -= 1<<i if n: # 可能会有剩余 res.append(n) print(res) ~~~