说到动态规划，就不得不提经典的背包问题了。在这篇BLOG中，我们将一同学习几种经典的背包模型，让你成为背包小能手。

背包问题

在学习各种背包问题之前，我们应该先了解一下什么是背包问题。

所谓背包问题，指的是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中：

对于选择方案我们当然可以暴力枚举，但一般背包问题的数据范围都较大，单纯的暴力枚举很可能会超时。所以在接下来的几个部分，我们就来一同学习一下几种经典背包问题的高效解决算法吧！

01背包

简化的01背包

在看正式的01背包问题钱，首先我们先来看看简化的01背包问题——装箱问题。

有一个箱子容量为V（正整数， 0＜＝ V＜＝ 20000），同时有n个物品（0＜ n＜＝ 30），每个物品有一个体积c[i]（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述：一个整数v，表示箱子容量；一个整数n，表示有n个物品；接下来n个整数，分别表示这n 个物品的各自体积
输出描述：一个整数，表示箱子剩余空间。
样例输入: 24 6
8 3 12 7 9 7
样例输出： 0

我们来分析一下这个问题，这个问题的原问题显然是 i 件物品选若干件组成的小于V的最大体积是多少？为了达到这个目标，我们用用可行性描述就可以了。我们用bool数组f[i][j]表示前i个物品能否放满体积为j的背包，我们枚举最后一次决策——第i个物品放还是不放！所以我们可以得到下面这个状态转移方程
f[i][j] = f[i-1][j](不放) || f[i-1][j-c[i]](放)
初值 f[i][j] = 0; f[0][0] = 1;

比如对于样例输入，我们就会得到下面这张表：

其实通过观察我们知道每一行的结果实际上只与上一行有
关，所以就可以01滚动——f[i][0,1] 一行记录前一行的值，另一行记录当前行的值……

不过对于本题更加常用的方法是就地滚动！！那么什么是就地滚动呢？就地滚动嘛，顾名思义就是用一个一维数组了！之前的状态和当前的状态都记在同一个数组里了！

但是简单的变成一维以后有可能会有问题的——比如，我们把代码写成这样：

for(int i = 1; i<= n; i++) {
    for(int j= c[i]; j <= v; j++) {
        if(!f[j - c[i]) f[j] = f[j - c[i]];
    }
}

假设第一个物品体积3,我们画出表就看出问题了：

这样一个物品就可能被算多次…………就不符合我们01背包一个物体只可以取一次或者不取。

那我们怎么办？我们可以改变内层循环顺序！我们把代码改成如下这样：

for(int i = 1; i <= n; i++) {
    for(int j = v; j >= c[i]; j--) {
        if(!f[j-c[i]]) f[j] = f[j - c[i]] ;
    }
}

假设在判断若干个物品后f数组如下表，我们需要决策的物品体积是5。就地滚动相当于把前一阶段的状态和当前阶段的状态放在了同一行。为了确保区分它们， 我们需要保证上一行的状态在j的左边，当前行的状态在j的右边：

这样我们就可以完成优化过的装箱问题啦。

正常的01背包

我们先来看看正常的01背包问题的问题描述。有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。 求解将哪些物品装入背包可使价值总和最大。

f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。那么对于物品i，仍然是有两种情况：
1.不放当前物品 f[i][j] = f[i-1][j]
2.放当前物品 f[i][j] = f[i-1][j-c[i]]+w[i]
所以我们统一起来这两种情况就有f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+w[i]}

我们来举个例子吧。假如N = 6 V = 12
费用c[i]：5 3 2 4 5 4
价值w[i]：10 7 4 3 17 8
那么我们通过上面的方法就可以列出下面这个表格：

在第6行中我们找到最大的数字32就是我们的答案。这里要注意我们最后的答案不一定在最右边！！我们要遍历最后一行找到最大的数才能得到正确的答案。

当然我们正常的01背包问题也是可以就地滚动的，所以总的代码如下所示：

for ( i = 1 ; i <= n; i++ ) {
    for (j=m; j>=c[i]; j--)`{
        if (f[j-c[i]] + w[i] > f[j]) {
            f[j] = f[j-c[i]] + w[i];
        }
    }
}

稀有的01背包

如果在刚刚正常的01背包的背景下，数据范围是N<= 20, V <= 10^9，这时我们该怎么办？

很显然这时的N<= 20，我们只要暴力枚举所有情况找到最优的那个就行啦，时间复杂度是O(2^N)，在N<= 20的情况下是完全没问题的。

史诗的01背包

我们继续在正常的01背包的大背景下，假如这时数据范围变成N<= 40,V <= 10^9，这时我们又该怎么办？

由于背包体积太大我们肯定不能直接动态规划，又由于N不算小，如果沿用刚刚稀有的01背包的O(2^N)的算法势必会导致超时，那我们该怎么办呢？

其实也很好想到。我们可以对这40个物品进行折半搜索。在学习广度优先搜索的时候你是否有这样的疑问——广度优先搜索都有双向广搜这种能让复杂度直接开根号的优化方法，难道深度优先搜索就没有吗？今天我就告诉你，是有的。和双向广搜有点异曲同工，这种方法叫做折半搜索。

什么是折半搜索呢？
顾名思义，就是将我们的枚举过程从完整的枚举整个数据集的情况；转化为将数据集平均分为前后两半，分别枚举后再考虑利用其他算法进行合并。其复杂度一般为O（C*2^(n/2)）。

所以回到这道题我们先把这40个物品分为前20个和后20个两组，分别搜索出这两组的所有情况分别存在数组a和b中。这时我们数组a和b都分别有2^20个元素，每个元素存有该种方案的空间花费和最后的价值。接下来我们就考虑如何进行合并。

我们先将数组a和b分别按照其方案的花费空间从小到大进行排序。我们用一个指针指向b数组的尾部。接着我们开始一个一个枚举a数组中的元素，假如我们当前枚举到a数组的第i位，我们就去判断，如果当前指针指向的b数组元素的空间花费加上a数组当前第i位的空间花费小于等于题目给出的空间就代表是合理的，那么我们就讲这个指针指向的b数组元素产生的价值丢进一个从大到小优先队列里，然后指针左移一位继续判断直到指针指向的点不满足上述条件。这时如果a数组选第i个元素，那么此时的最大值就是a数组第i个元素产生的价值加上我们优先队列的队首元素。我们将当前状态的最大值与答案比较更新答案。最后输出就可以啦。

传说的01背包

我们继续在正常的01背包的大背景下，假如这时数据范围变成N<= 100,V <= 10^9，这时我们又该怎么办？

其实我们可以用数学证明出来，假如忽略V(V很大)，这道题是不存在关于N的多项式时间复杂度的解法的。那是不是代表这道题就是不可做题呢？那当然不是。

我们考虑这种情况，我们假设f[i][j]代表前i个物品中任意选择恰好填满j的空间大小带来的最大的价值。那假如此时我们循环到i = 10,我们发现循环过后f[10][50]=100，f[10][60]=60，那是不是这个f[10][60]=60就完全没有存在的必要啊。你看他空间又耗费的大，带来的价值又少，f[10][50]完全是f[10][60]的上位取代。就好像如果你有一个学弟，他比你年轻还比你强，那你就永远打不过他了。

我们不能使用动态规划的原因是空间太大了。这时如果我们把所有像f[10][60]这样价值比不上空间比他小的方案的方案给丢弃掉的话，只要能丢弃到只剩下原来方案的1/10，空间就足够了（可以证明是很难卡掉的，除非构造每10个数递增一下的f数组）。那接下来的问题就是如何让体积大价值小的方案多出现呢？很简单我们按照物品的性价比（价值/体积）从大到小排序再进行背包，这样就能让体积大价值小的方案多出现。

我们最后还剩下一个问题，我们如何写代码才能实现上述的“丢弃”操作呢？其实也不难，我们开一个Node类型的map，Node类型包含两个数v和value，每次操作假如我们想要插入(vi, ci),我们就只要在map中二分查找出第一个体积小于等于vi的对（vi', ci'），然后比较ci和ci'的大小就好啦，如果ci大于ci'才插入否则抛弃。然后在插入后，我们还要去不断看看第一个体积大于等于vi的对（vi', ci'）然后比较ci和ci'的大小就好啦，如果ci大于ci'我们就抛弃（vi', ci'）这个对，然后继续看看现有的看看第一个体积大于等于vi的对（vi', ci'）重复上述操作直到没有对了或者ci=小于ci'了。

完全背包

学习完了01背包接下来让我们来看看完全背包问题。我们先来看看完全背包的问题描述。

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci ，价值是 Wi 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

于01背包不同的是，在完全背包中，每件物品不是只有取和不取两种状态了，取的时候还要考虑取多少件。我们还是来考虑一下动态规划的四步法：

第一步：确定状态
f[i][j] 依然表示前 i 种物品恰放入一个容量为 v的背包的最大权值。
第二步：确定状态转移方程
对于每种物品，我们可以增加一维枚举k-表示这个物品我们取k个的情况，所以转移方程就如下：
f[i,j] = max（f [i -1,j-k*c[i] ] + k * w[i])(0 <= k*c[i] <= j)
但这时时间复杂度O(V*Σ(V/c[i]))，这样子的话绝大部分题都是过不去的，该怎么办呢？

还记不记得之前讲01背包的就地滚动的有一段错误代码：

for(i=1 ; i<= n ; i++) {
    for(j= c[j]; j<v ; j++) {
        if(!f[j-c[i]) f[j] = f[j-c[i]];
    }
}

这段代码导致所有的物品都被算了多次……这不正是完全背包所需要的么？我们稍作修改得到完全背包的代码：

for(i=1 ; i<= n ; i++) {
    for(j= c[j]; j<v ; j++) {
        if(f[j-c[i] + w[i] > f[j]) f[j] = f[j-c[i]] + w[i];
    }
}

举个例子吧，假设第一个物品体积为3，价值是5，那么我们就能通过上述代码得到以下表格：

这正是我们完全背包想要达到的效果。

多重背包

有了完全背包的基础，接下来我们来看看多重背包。

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

我们很容易想到最朴素额状态转移方程和完全背包的时间复杂度高的算法一样，我们枚举每种物品放多少个：
f[i][v]=max{f[i-1][v- k*c[i]]+k*w[i]|0<=k<=n[i]}
这样的话复杂度是O(V*Σn[i])。比较大，需要优化……

我们考虑转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题当然这样直接求解的复杂度仍然是O(V*Σn[i])。接着我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。

讲到这里我们的方法就呼之欲出了：我们将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用
和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就
将这种物品分成系数分别为1,2,4,6的四件物品。

那将n[i]拆成1,2,4,...,2^(k-1),n[i]-2^k+1，（k是满足n[i]-2^k+1>0的最大整数）道理何在？

首先 1+2+4+...+2^(k-1)+n[i]-2^k+1 = n[i] 这就保证了最多为n[i]个物品。其次1,2,4,……,2^(k-1),可以凑出1到2^k – 1的所有整数（联系一个数的二进制
拆分即可证明）。最后2^k……n[i]的所有整数也可以用若干个上述元素凑出（我们设分组的最后一个数n[i]-2^k+1为x。我们想凑出2^k……n[i]中的任意一个数假如是y吧，我们可以先取一个x，剩下还有y-x要取，显然y-x<=2^k – 1,根据上一步我们知道用前面的数是一定可以凑出1到2^k – 1的所有整数的，所以我们就知道y一定可以被凑出来，换句话说2^k……n[i]中的任意一个数也可以被凑出来。要不然可以理解为凑n[i]-t, 而n[i]为上面所有数的和， t则是一个小于2^k 的数，那么在所有的数中去掉组成2^k 的那些数剩下的就可以组成n[i]-t了）。

这样我们就能用log(n[i])个数的组合表示1-n[i]中的任意一种情况，所以我们的复杂度也变成了O(V*Σlogn[i])，时间大大减少。我们的多重背包也顺利解决了。

二维费用背包

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。

同样我们可以设设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}分别对应第i件物品取或者不取的状态。

其实二维三维甚至是n维都是类似的，都是在我们的状态中增加一个维度其他不变就好了。当发现由熟悉的动态规划题目添加限制条件变形得来的题目时，可以尝试在原来的状态中加一维以满足新的限制条件。

分组背包

最后我们来看看分组背包。有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

本题和前面的题最大的不同是——每组物品有若干种策略：选择本组的某一件，或者一件都不选。其实也是类似的。

我们设f[k][v]表示前k组物品花费费用v能取得的最大权值，那么根据第k组选不选选哪个的分类讨论就能得到方程f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}
使用一维数组滚动的伪代码如下：

for 所有的组k {
    for v=V..0 {
        for 所有的i属于组k {
            f[v]=max{f[v],f[v-c[i]]+w[i]}
        }
    }
}

“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

结语

通过这篇BLOG，相信你已经掌握了这几种经典背包问题的模型。对于动态规划的问题了解原理是远远不够的，最重要的还是要多做题！最后希望你喜欢这篇BLOG！