背包九讲—简单背包
背包九讲
背包问题是一种动态规划算法的衍生问题。它可以被看作一种独立的题型，也可以看作是一种线性动态规划。学好背包、学会背包，对于深入理解动态规划算法有着极大的好处，并能帮助理解一些更深层次的动态规划问题。
背包问题分支有许多子问题。每一个问题有一个相对独立又互相关联的解决方法。在本篇随笔中，我使用了一个“古老”的标题：“背包九讲”。在这九个讲解块中，我加入了我对背包问题的一些个人理解与技巧应用经验。如有谬误，烦请有缘读到这篇博客的各路大佬指正。
那么就开始吧~
第一讲 0/1背包问题
题目类型
有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费体积是\(v[i]\)，价值是\(val[i]\)，求将哪些物品装入背包可使价值总和最大。
问题解析
0/1背包问题是最基础的背包问题，可以这么说：0/1背包是所有背包的祖先。因为0/1背包是用线性动归的思路来求解的，而其他的背包是用0/1背包的思想来求解的。所以，为了解决这个问题，我们来用线性DP的基本内容来思考。
- 决策
因为是动态规划，所以我们在思考的时候一定要牢记DP的两个性质：无后效性和最优子结构，也就是说，设置决策是解决动归的灵魂。回归0/1背包的问题，我们容易得出一个性质：每件物品只会面临一个决策：放还是不放。那么，我们接下来的部分就可以用这两个选择来继续进行。
- 状态
状态的定义建立在子问题的基础上，针对0/1背包，我们的状态被设置成：\(dp[i] [j]\)表示前\(i\)件物品中任选若干件放入容量为\(j\)的背包所能得到的最大价值。
- 状态转移方程
\]
我们有必要好好理解这个方程。这个方程表示的是一个决策的过程，因为我们在决策一件物品放或不放的时候，牵扯到的数据只是在放它之前的那个状态。那么易知：如果不放的话，那\(dp[i] [j]\)就是\(dp[i-1] [j]\)，因为容量没有变，如果放了的话，那么就需要在原来的背包中腾出一个\(v[i]\)那么大的空位，否则这个新物品将无处可放。当然，如果放了这个物品，那么还需要加上\(val[i]\)。
- 答案
综上所述，最终要求的答案就是\(dp[n] [V]\)。
空间复杂度的优化
我们发现，上面的\(dp\)数组是一个二维数组，那么假如背包最大容量和物品件数都特别大的时候，这样的空间复杂度肯定会爆炸。所以我们需要采取手段来优化它的空间复杂度。01背包的空间复杂度优化方式有两种：一种是滚动数组优化，另一种是压维优化。
我们会发现，0/1背包的状态转移方程只用到了\(dp[i-1] [j]\)的数据。也就是说，我们在求取答案的时候，\(1-(i-2)\)的数据是啥用没有的。那么我们考虑不再存储这些数据，而将数组“滚动”起来，依次覆盖上一次用不着的数据，这样就可以把dp数组的第一维只开2位，而完成0/1背包的DP操作，大大地降低了空间复杂度。
在此我不讲解滚动数组的代码实现，因为特别麻烦。但是又不得不说这个滚动数组，因为这是理解下一个优化：压维的重要知识铺垫。
我们来看一下压维操作。
因为每种物品只有放或者不放这两种可能，所以我们在处理的时候可以把存物品的那一维省略，直接用背包容量来进行DP，更大地压缩了空间复杂度。
实现的时候非常简单：
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
dp[j]=maxn(dp[j],dp[j-v[i]]+w[i]);
细心的读者可能已经注意到了，这里的第二维\(j\)是从\(V\)到\(V[i]\)开始枚举的。这是为什么呢？
我们的外层循环进行的是逐物品枚举，而内层循环只起到一个作用：持续更新当前容量的价值最大值。所以状态转移方程的意义就是：当前物品的放与不放是否会对当前的答案产生影响。这就是0/1背包的压维优化了。
例题推荐
第二讲 完全背包问题
题目类型
有\(N\)种物品和一个容量为\(V\)的背包，每种物品有无限件可用。第\(i\)种物品的费体积是$ v[i]\(，价值是\)val[i]$，求将哪些物品装入背包可使价值总和最大。
问题解析
本问题可以看作是0/1背包的加强版本，因为每种物品都有无限件可以选择，这样就会给我们0/1背包求解的过程带来许多麻烦。比如：它的决策过程已经不是取或不取两种，而是取1件、2件、3件、不取等很多种。那么我们仍然试着写出状态转移方程，按照0/1背包的思路，令\(dp[i] [j]\)表示取前\(i\)种物品放入一个容量为\(j\)的背包里的最大值。即有：
\]
\]
我们容易发现这是一个三重循环，在数据稍微大一点的情况下，时间复杂度就受不了了。所以，我们必须对以上思路进行优化。
完全背包到0/1背包的转化
在讲解0/1背包的时候说过，0/1背包是最基本的背包。不仅是完全背包，之后的许多背包都要转换成0/1背包进行求解。
在完全背包问题中，有一个显然的性质：每种物品最多选择\(V/v[i]\)件，于是我们把这种物品拆成\(V/v[i]\)个体积、价值均相等的物品，这样就转化成了0/1背包问题。可以使用0/1背包问题的转移来求解。
倍增优化
完全背包的接替模型其实是直接转换成0/1背包，因为总体积是\(V\)，对于每种种类，最多只能放\(V/v[i]\)个物品，就可以直接转换成0/1背包。
但是这个转换很麻烦，如果再放到一维数组，很容易爆炸，所以我们使用倍增思想进行优化。倍增思想是一个很有用的东西，我们可以把刚才的\(n\)个满足\(V/v[i]\)种类的物品给压缩，怎么做呢？
举个例子： \(V=22，v[i]=3,w[i]=2;\)
用刚才说的\(V/v[i]\)就拆成了\(7\)个相同的物品。
用倍增优化呢？
我们就可以拆成空间为\(v[i]\times 2^k\)，价值为\(w[i]\times 2^k\)的若干件物品，其中\(k\)满足小于\(V\)的要求。
所以用这种方法，我们就一共拆出来了3件物品，仅仅三件！！！
体积为3，6，12，价值为2，4，8。
这也是完全背包最常用的模板。
代码如下：
for(int i=1;i<=n;i++)
for(int j=v[i];j<=V;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
细心的读者又会发现：这个模板和0/1背包的模板只有第二层循环的循环次序不一样。那么为什么上面的是0/1背包，这个就变成了完全背包呢？这是因为我们在完全背包中要保证每一个子问题的状态是由它的前一个状态递推而来的（0/1背包拆分之后，每种物品选不选，选几个，都是影响后续决策的），所以我们要正着推。而0/1背包则正好相反，我们的每个物品的数值是确定的，为了符合无后效性，显然要从后往前递推。这其实也是完全背包和0/1背包本质上的区别。
例题推荐
第三讲 多重背包问题
题目类型
有\(N\)种物品和一个容量为\(V\)的背包，每种物品有\(p[i]\)件可用。第\(i\)种物品的费体积是$ v[i]\(，价值是\)val[i]$，求将哪些物品装入背包可使价值总和最大。
问题解析
一种好想的基本方法是直接转化成0/1背包求解，因为题意已经告诉我们每种物品的件数，所以我们可以直接把它拆成\(p[i]\)个相同的物品，然后进行求解。
例题推荐
第四讲 混合背包问题
题目类型
前面三个背包的混合版。
问题解析
原讲解里有一句话让我印象深刻：所有的复杂问题都是由一堆简单问题拆分而成的。那么，我们解决这个问题的时候也应该把问题拆分成若干的简单问题，然后进行求解。
- 0/1背包与完全背包
这种结合有两种物品，一种只能用一次，一种能用若干次。那么根据题目中的意思，我们可以分别处理两种不同的问题，即分别解决两种物品的背包。（代码实现就是顺逆序循环的灵活调用）
- 带有多重背包的问题
思路和以上的差不多，也是拆分求解。如果是多重背包，就用单调队列来求，复杂度很优。