动态规划入门——经典的完全背包与多重背包问题
今天是算法数据结构专题的第13篇文章，也是动态规划专题的第二篇。
上一讲当中我们一起学习了动态规划算法中的零一背包问题，我们知道了所谓的零一背包是指每一种物品只有一个，所以它的状态只有0和1两种，即拿或者不拿。而今天我们要来讨论物品不止有一个的情况，物品不止有一个也分两种，一种是不作任何限制，要多少有多少，这种称为完全背包问题，另一种是依然有个数限制，这种称为多重背包问题。
我们一个一个来看，我们先从其中比较简单的完全背包开始。由于我们这是一个连续的专题，没有看过上篇文章或者是新关注的同学可以移步我们专题的第一篇：
完全背包
在之前的文章当中，我们阐述了动态规划当中状态和决策以及状态转移的相关概念。在背包问题当中，背包的容量是状态，而选择哪个物品进行获取则是决策，当我们制定了一个决策之后，背包会从一个状态转移到另一个状态。而动态规划算法就是枚举所有状态和决策，获得所有的状态转移，并且记录这个过程中每个状态能够获得的最优解。
在之前的文章当中，我们先遍历了所有的决策，然后再枚举了所有的状态，计算在决策下进行转移之后得到的结果。在之前的零一背包问题当中，由于我们每个物品只能获取一个，如果在前面的状态执行了决策，那么后面的状态则不能进行相同的决策。这也就是动态规划的后效性，而在完全背包问题当中，我们去掉了这个限制，也就意味着决策之间不再有后效性，一个决策可以重复应用在各个状态当中。
所以如果你能理解上面这段话，那么整个算法其实非常简单，几乎就是零一背包的代码。只不过我们把其中倒叙遍历的背包状态再”修正“回来。
之前我们为了避免物品的重复获取，所以采用了倒叙遍历的方法，如今我们不再对数量进行限制，意味着我们可以自由地采取决策进行转移。要做到这点，其他的代码都不用修改，只需要将第二重循环枚举的状态，再换成从0开始的正向遍历即可。
dp = [0 for _ in range(11)]
items = [[6, 10], [5, 8], [5, 9]]
# 遍历物品
for v, w in items:
# 遍历背包空间（状态）
# 更新vp+v的状态，即当前容量放入物品之后的状态
for vp in range(0, 10-v+1):
dp[vp+v] = max(dp[vp+v], dp[vp] + w)
print(max(dp]))
如果你还没能完全理解其中的逻辑，我们可以对照一下代码再来理解一下。在第一种循环当中，我们遍历了所有的物品，每一个物品对应了一种决策。每一个决策可以应用在各个状态上。
比如第一个物品是6， 15，代表它的体积是6，价值是15。那么我们遍历所有能够应用这个决策的状态，也就是在不超过背包容量的情况下能够放下的状态。显然对于一个体积是6的物品来说，只有0到4的状态可以放下。比如说我们选择状态2，状态2放下了这个物品之后，自然会转移到状态8，因为体积增加了6。有可能这个决策会使得状态8获得更好的结果，也有可能不会，如果会的话我们就更新一下状态8记录的值。这个从一个状态采取决策到另一个状态的过程就是状态转移。
完全背包就是零一背包的无限制版，从原理上来说，两者的思路和做法基本上是一样的。如果你能理解零一背包，那么完全背包对你来说也一定不在话下。
细小的优化
在完全背包当中，由于所有的物品都可以无限获取。所以我们可以引入一些零一背包不能进行的优化，比如对于同样体积的物品而言，我们可以只保留价值最高的物品，将其他的物品过滤掉。这个思路很朴素，我想大家应该都能理解。
比如两个物品体积都是3，一个价值是4，另一个价值是3，我们完全可以忽略价值是3的那一种。因为两者带来的状态转移是一样的，但是明显前者收益更好。而这个优化在零一背包当中不可行是因为每个物品只有一个，很有可能会出现两者都要的情况。在完全背包当中则没有这个问题。
多重背包
和零一背包以及完全背包相比，多重背包要难上一些，它的解法也非常多样。我们今天先来看一个相对比较简单的方法。
同样，我们从最简单的方法开始讲起。最简单的方法当然就是将多重背包蜕化成零一背包来解决，比如一个物品最多可以拿N个，我们就把它拆成N个物品，这样每个物品最多拿一个，相当于我们可以最多拿N个。这个思路应该很简单，大家都能想明白，但是有个很大的问题，就是复杂度。当然我们可以根据背包的体积做一些优化，比如当物品的数量很多并且超过了背包容量的时候，我们可以把超过容量的数量去掉，但是整体的复杂度还是很高。尤其是当我们背包容量很大的时候。
那么，我们怎么来解决这个问题呢？
这里要介绍一个比较通用的算法，这个算法可以用来优化很多问题，也是很多算法的思想。它就是二进制表示法。这个方法我们在之前的文章当中曾经讲到过，思想非常简单，但是非常实用。
二进制表示法
所谓二进制表示法就是将一个int类型的数表示成二进制，整个算法的思想就是这一句话，所以我想大家应该都能理解。但是我们为什么要将一个int转成二进制，以及转成二进制之后怎么样来优化算法，这个才是我们想知道的，也才是算法的核心重点，不要着急，我们一点点来说明。
我们都知道在计算机系统当中都是以二进制存储的所有数据，最典型的就是整数。一个32位的int，可以表示最大21亿的整数。这个都是我们已知的，但是换一个角度来看，一个21亿的数最后用32个二进制位就表示了，其实非常惊人。为什么说二进制是一个非常伟大的思想？不在于它难，而在于它高效地压缩了数据。
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
# 物品，分别是数量，体积和单位价格
items = [(10, 3, 5), (5, 6, 3), (2, 2, 4)]
volume = 20
dp = [0 for _ in range(volume+1)]
new_items = []
for i in items:
# 二进制拆分
new_items.extend(binary_divide(*i))
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[20])