爱华网本文参照了dd的背包九讲，算是一篇读书笔记。背包问题是体现动态规划思想的一类基本问题，可以有很多的变化。
1.01背包和动态规划
一般的描述如下：给定一个体积为V的背包，然后给定1…n件物品，第i件物品的体积为V[i]，价值为W[i]。要求选定若干件物品放入背包，使背包内物品的价值最大。
以上的问题被称为01背包问题，因为每种物品只有一件，它只有放和不放入背包两种情况，对应0和1两种决策。01决策，在数据量很小的情况下，考虑暴力搜索，搜索的次数是2^n，通常这都不是一个很好的办法。如果不考虑动态规划，我们的第一反应可能是贪心策略。很明显，体积小价值高的物品与体积大价值低的物品相比，应该先放入背包。不过，这种策略对体积大价值也大或者体积小价值也小的物品就无能为力了。使用这种方法O(n^2)先去除明显不合理的数据再暴力搜索。另外，或许你会用w[i]/v[i]来排序，实际上这种方法是错的，因为总的价值仍然受到背包体积V的影响。因为很可能w[i]/v[i]较高的物品装不满背包，使得背包的总价值比较小。
切入正题，我们来考虑动态规划。能用动态规划解决的问题一定能把问题分解为一系列互相联系的单个阶段问题。并且子问题之间满足最优化定理：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k <n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。就是说，无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。最后还要满足无后效性，无后效性是指：下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结。
以上三种要素构成了动态规划：可分解为相互关联的子问题，最优化定理，无后效性。从另一个方面看就是状态，阶段和决策。
我们这样考虑背包的状态：放入第n个物品时，背包的体积为v时，它的最大价值为dp[v][n]。初始状态为dp[0][0]=0。如果一件物品有放入和不放入背包两种方案，那么要决定第n+1件物品是不是向其中放入时。dp[v] [n+1] = max {dp[v][n],dp[v-v[n+1]][n]+w[n+1]}。这就是状态转移方程。从1到n件物品，每件物品都从1到V遍历一次背包体积，时间复杂度是O（nV）。空间复杂度似乎也是O(nV)，但实际上可以通过适当的方法将空间负责度压缩为O(V)。方法就是对每件物品，由V到1的遍历背包的体积。这样dp[v-v[n+1]][n]肯定还没有被第n+1件物品影响。
至此，01背包问题得到圆满的解决。
2.完全背包
将01背包的问题进行一点变化，每件物品可以取任意多件，而非仅仅一件。就是说，我们有n种物品，每种物品i的体积为v[i],价值为w[i]。背包体积仍然为V，求解让背包内物品价值最大的方案。
有了01背包的基础，我们会想把完全背包转换为01背包，最朴素的想法就是把n种物品变为m件物品，只不过其中某些物品的体积和价值完全相同。m=sum(n/v[i])件。当v[i]比较小时m就会变得很大，搜索效率降低。我们换一种思路，将n种物品拆分时，拆成1，2,4,8…2^k件物品，直到sum(2^k) * v[i] <=n。最后一件物品的体积是{n-(sum(2^k) * v[i])}*v[i]，当然价值也是相同的倍数。可以使用2进制编码的理论对此进行证明：0到（2^n-1）之间任何一个数都可以用长度为n的01串表示。这样m的值就变为sum(logn/v[i])，从而使得运算的复杂度大大降低。
其实针对完全背包，还有一种更好的思路：将01背包中的内层循环改为1…v。在v较小时dp[n-1]和dp[n]实际上是相同的。仍然是01背包的复杂度。
3.多重背包
对完全背包的问题进行进一步的修改：每种物品的数量不是无限的，而是有限的。这时候可以采用对于完全背包问题中，对物品进行2进制划分的做法。背包九讲中提到存在一种算法可以使得复杂度同样降低到O(nV)。
4.混合背包
混合了以上三种背包问题：有些物品是有限的，有些物品是只有一件，有些物品有若干件。解决的关键在于控制好内层循环，根据不同的物品性质采用不同的遍历顺序。
