动态规划之01背包学习

关于动态规划的那些事系列–01背包问题

01背包问题是动态规划的最经典的问题，没有之一，毫不夸张的说，背包问题非常重要。对01背包问题进行不断地思考，我忽然发现有些东西还真挺有趣。也觉得颇为神奇。

可能很多人并不知道为什么叫做“01”背包，其实0和1分别代表了对于此物体的选择，0是不选，1是选择。对于经典的一定容量选择价值最大物品组合的问题，可以转化为以下的定义：（有n件物品，第i件物品的体积为wi，价值为vi， 背包的最大容量为W）

xi = {1, 0}, sum(xi * wi) <= W
求 max{sum(xi * vi)}

如果这样的物品是可以分割的那么我们可以使用贪心策略，一直选择性价比最高的物品就行了，那么如果不能这样做，对于一件物品，要么全拿，要么不拿，该怎么得到最优的策略？

这时候不妨自己去思考一下。。。。（还真难想）

后来运筹学的大佬提出了著名的动态规划的思想，但是什么叫做动态规划呢？恕我直言，严格上说动态规划其实就是一种策略思想，并不是一种算法。我更喜欢直接叫做“状态递推”。。。回到背包问题。。。。

我们定义dp[i][j]表示对于前i件物品容量为j的背包可以得到的最大权值。

dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]]+v[i]}

这就是这道问题的状态转移方程。
于是这个问题不就成了一种简单的递推题了吗！
可是这状态转移方程可是神学啊！怎么得到的？

文字解释（好懂）：

dp[i-1][j]表示对于第i件物品我们不取。
dp[i-1][j-w[i]]+v[i]表示对于第i件物品我们取

大部分人的问题是第二个状态的理解。其实也不难，对于容量为j的背包，我们如果装下第i件物品（包含了这件物品），就要至多在容量为j-w[i]的背包装，对于这个问题，我们知道容量肯定是越大越好，所以在没有装下第i件物品的状态中（没有包含第i件物品的背包），dp[i-1][j-w[i]]一定拥有最大的权值。

伪代码：

F[0, 0..V ] ← 0
for i ← 1 to N
	for v ← Ci to V 
		F[i, v] ← max{F[i − 1, v], F[i − 1, v − Ci] + Wi}

以上方法的时间和空间复杂度均为 O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 O(V)。

这里主要用到了一个叫做滚动数组的玩意。（顾名思义，在数组上面不断发生数值更新。保留下最新的数据结果，而之前的数据会被覆盖掉。可以很大程度优化空间，但是不能得到之前的结果）

其实也不难，通过状态转移方程可以很容易知道每一个状态都和上一行的状态有关，于是我们可以将第一维去掉，留下第二维。这样的话就可以得到下面的伪代码：

F[0..V ] ←0
for i ← 1 to N
	for v ← V to Ci 
		F[v] ← max{F[v], F[v − Ci] + Wi}

这里有一个很奇怪的问题：为什么v是反着遍历的？

其实这里主要是不能违背一个原则：推导的状态必须是由已经计算得到的前一个阶段的状态得到的。（说白了就是在求dp[i][…]时，你后面的那些状态必须是dp[i-1][…]的。）

如果是顺序遍历，那么由于是一维的数组，那么求后面的状态的值时，你用到的不就是现在这个阶段的状态吗，之前阶段的状态已经被刷新了！！

但是巧妙的是，反过来遍历就不会有这样的问题。。。。

模型总结：

对于一种问题，有n种选择，每一种选择会带来一定的代价和具有一定的权值（正数），每一种选择只能选择一次，在一定代价内得到的最大权值。