背包dp

一、前言

本章主要整理有关背包dp问题的汇总，其实背包dp应该已经是超级经典的一类问题了，相信很多人已经做过很多背包问题了，模板肯定烂熟于心，但是本人而言，虽然写的很顺手，但是还是把一些模板整理一下，自己写一遍会更加有助于理解吧。而对于背包问题无疑有几个分类01背包，完全背包，多重背包，分组背包等,而这些问题有一个共同点，就是有多个物品，每个物品有着对应的体积和价值，而就是这三类衍生很多很多的问题。

本章题大多来源于ACwing,欢迎大家来这个平台一起学习算法！！

二、题目汇总

我们这里用w[i] (weight)代表一个物品体积，v[i] (value)代表物品价值

①ACwing 2.01背包

(1)题目描述

(2)dp分析

为什么选i的那一个状态是如上的呢？

按照字面理解，假设我们选择了第i个物品，那么我们就相当于选出前(i-1)个物品，但是重量要减去第i个物品的最大价值的一个假背包然后拿假背包的最大价值加上我们第i个背包的价值，就会得到选择i的价值。

状态转移方程：
$$
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i])
$$
如果要优化成一维的呢？

这里一直是01背包和完全背包大家搞不清楚的地方。在后面推导完全背包的时候，大家应当会有更好的理解。在这里先说01背包的优化。我们可以看到，01背包的二维推导的时候，右边的等式都是由i-1作为第一维，形象来说，也就是本层的所有值都是由上一层的值推导而来的，因此我们如果把第一维去掉，我们一定要保证的是本层状态在推导的时候，用到的值一定是上一层还没有被更新的状态，也就是说我们在循环j的时候一定要从大到小进行，这样就能够保证大的j在推导的时候用的是上一层j-w[i]的值，而如果我们从小到大，假设其中j为5的时候，被更新了，那么当j更大的时候利用这个j为5的值来更新，就不能保证值是上一层的，也就是最后的答案就不一定是正确的了！

(3)完整AC代码

//没有空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1005;
int w[N], v[N];
int f[N][N];
int main() {
    //n代表物体数量，m代表最大体积
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if(j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}
//进行空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1005;
int w[N], v[N];
int f[N];
int main() {
    //n代表物体数量，m代表最大体积
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; i ++ ) {
        for(int j = m; j >= 1; j -- ) {
             if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}
//对比一下上面代码，基本上就是删掉一维，然后改变j的循环顺序就好了

---

②ACwing 3.完全背包

(1)题目描述

(2)dp分析

分析一下选i的集合计算

假设我们当前选到的价值为j,当前的物品体积为w，价值为v，最多可以选择k个i才不会让(j - k*w) < 0。

那么我们选择i就有k种方式也就是有下面的状态转移方程

状态转移方程：
$$
f[i][j]=max\begin{cases}f[i-1][j], 不选择i这些物品 \\
f[i-1][j-kw[i]]+kv[i], 选择k个i物品且(j-kw[i])>=0
\end{cases}
$$

​
​

因为我们多了一个k，所以也就是我们会多出一层循环，去循环k的数量，如果是这样的话，我们的时间复杂度会达到O(n^3)最多，那么我们题目的n为1000，也就是这个时间复杂度是过不了的，所以我们要想办法去优化掉这个k这一层循环？怎么优化呢?很多地方在讲到这里的时候并不会给出一个推导，在此给出一个推导。

我们对比一下两个式子
$$
f[i][j]=max(f[i-1][j],f[i-1][j-w]+v,f[i-1][j-2w]+2v,···,f[i-1][j-kw]+kv) \\
f[i][j-w]=max(f[i-1][j-w], f[i-1][j-2w]+v,···,f[i-1][j-kw]+(k-1)v)
$$
可能光这样看不是特别形象，我们把两个式子的一些式子对齐看看
$$
f[i][j]=max(f[i-1][j],f[i-1][j-w]+v,f[i-1][j-2w]+2v,···,f[i-1][j-kw]+kv)\\
\ \ \ \ \ \ \ \ \ \ \ \ \ f[i][j-w]=max(f[i-1][j-w], f[i-1][j-2w]+v,···,f[i-1][j-kw]+(k-1)v)
$$

f[i] [j]=max(f[i-1] [j],f[i-1] [j-w]+v,f[i-1] [j-2w]+2v,···,f[i-1] [j-kw]+kv) ①
f[i] [j-w]=max(/ / / /f[i-1] [j-w], f[i-1] [j-2w]+v,···,f[i-1] [j-kw]+(k-1)v) ②

这样再看看呢，我们可以发现$f[i][j]$推导式的第二项和我们给的第二个式子②是有关系的，而这个关系恰好就是第二个式子加上一个v

有了上面的关系之后，我们的状态转移方程就可以写成

状态转移方程：
$$
f[i][j]=max(f[i-1][j], f[i][j-w]+v)
$$
至此，我们可以惊奇的发现，我们把k这一维消掉了！而我们对比一下这里的状态转移方程和我们01背包的状态转移方程。
$$
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]) (01背包)\\
f[i][j]=max(f[i-1][j], f[i][j-w[i]]+v[i])(完全背包)
$$
我们又可以惊奇的发现，竟然只有一个地方不一样!!也就是推导式子的第二个维度，01背包是通过上一层进行一个推导，而完全背包是通过本层进行推导！也就是说，我们的完全背包是通过本层已经推导出来的值去推导后面的值，也就是说我们在循环j的时候应该从小到大，大的那一个j应该是从之前某个小的j中推导出来，也就是小的j是需要先被推导好的！这也解释了我们的完全背包中每个物品数量是无限的！

(3)完整AC代码

//不进行空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1005;
int f[N][N];
int w[N], v[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ){
            f[i][j] = f[i - 1][j];
            if(j >= w[i]) f[i][j] = max(f[i][j], f[i][j - w[i]] + v[i]);
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}
//进行空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1005;
int f[N];
int w[N], v[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ){
            if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

(4)对于01背包和完全背包的总结

大家可以看到，两个背包的代码长得几乎是完全一样的！都是就是因为内层推导时候的不同，导致推导式稍微有一些区别，包括我们如果优化成一维背包的话，j的循环顺序的不同，这一点也是很多(包括我在内)的初学者经常比较不清楚的地方，也许之前学习背包的时候会经常用感觉去想这个问题，但是这一次利用数学推导去证明一下，我发现还是受益匪浅的！

③ACwisanng 3.多重背包

(1)题目描述

(2)dp分析

由于后续的背包模板都是由前两个背包进行扩展，后续直接给出状态转移方程。

状态转移方程：
$$
f[i][j]=max\begin{cases}
f[i-1][j], 不选择i这些物品 \\
f[i-1][j-kw[i]]+kv[i], 选择k个i物品且1\le k\le s[i]&& (j-kw[i])>=0
\end{cases}
$$

(3)完整AC代码

//不进行空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 105;
int f[N][N];
int w[N], v[N], s[N];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i] >> s[i];
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            for(int k = 1; k <= s[i] && j - k * w[i] >= 0; k ++ ) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}
//进行空间优化
//关注我们的状态转移方程和01背包是一致的，所以j的循环顺序从大到小哦!
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 105;
int f[N];
int w[N], v[N], s[N];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i] >> s[i];
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = m; j >= 1; j -- ) {
            for(int k = 1; k <= s[i] && j - k * w[i] >= 0; k ++ ) {
                f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);
            }
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

(4)二进制优化

证明：

对于这个题目我们发现n是100，所以呢三次循环的时间复杂度是可以过得去的，那么如果我们的n为1000呢?显然三次循环就过不去了，那么我们应该怎么办呢？

正如这里所说，我们可以利用二进制进行优化，对于这个优化。我先简单来说一说，就是我们把一个物品看成多个物品，然后这些多个物品是有他们本身的价值的。假设我们一个物品他有10件，那么我们可以利用2的次方去表示他。
$$
10=2^0+2^1+2^2+3
$$
也就是说，我们把10件物品拆成1，2，4，3件物品，为什么后面不是加$2^3$次方呢?首先10不会等于这些数相加，其次如果我们这样拆分，我们可能在计算这件物品的时候，最多就不再是10件了！那么把10件物品拆分后，我们得到了另外的4件物品，这四件物品的体积分别为1w,2w,4w,3w;价值分别为1v,2v,4v,3v。接下来我们就考虑我们怎么能把10件物品选择的每一种情况都考虑到呢？

观察10以内的拆分
$$
1=1,2=2,3=3,4=4, \\
5=1+4,6=2+4,7=3+4 \\
8=1+3+4,9=2+3+4,10=1+2+3+4
$$
从上面的式子看出来，选择这四种东西的不同选法可以拼接出我们选择10件物品的不同选法，为什么按照我们的拆分一定可以呢？

首先我们去考虑一下如果恰好一个数能够完全拆分成多个2的幂次方

比如7的二进制表示是111,也就是$7=2^0+2^1+2^2$,那么1,2,4的那一为有或无构成的数就可以形成7以内的任何数。好那么我们在考虑10，10的二进制表示是1010,毋庸置疑的是，10是可以由我们拆出来的所有数表示出来的，想了一下，如果我们正着推很难推出我们想要得到的结论，所以我们不妨反过来推导。正因为某个正数n必定介于$2^0 到 2^k$之间，假设我们这个数表示成$2^0+2^1+···+2^{k-1}+s$,其中s这个数是这个数减去前面的和，此时我们想一下$2^{k-1}到2^k$次方之间的所有数能不能被表示？

此时我们假设其中的一个数为num,num介于$2^{k-1} 到 正数n$之间， 那此时必定有
$$
0 \lt n - num \lt 2^{k-1}
$$
这也就告诉我们，如果我们用n减去前面已经用二进制表示出来的数的一个集合，必定是可以凑出我们的num的。比如
$$
9 = 10 - 1, 8 = 10 - 2
$$
至此二进制优化就是一个正确的写法。

时间复杂度： $O(\sum_{i=0}^{n-1}mlogs[i])$或者$O(nlogm*m)$

完整AC代码

//不进行空间优化，可能会爆空间
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 11005, M = 2005; 
int f[N][M];
int w[N], v[N];

int main() {
    int n, m;
    cin >> n >> m;
    int cnt = 1;
    for(int i = 1; i <= n; i ++ ) {
        int ww, vv, ss;
        cin >> ww >> vv >> ss;
        int flag = 1;
        while(ss - flag >= 0) {
            w[cnt] = ww * flag;
            v[cnt] = vv * flag;
            ss -= flag;
            flag *= 2;
            cnt ++ ;
        }
        if(ss) {
            w[cnt] = ww * ss;
            v[cnt] = vv * ss;
            cnt ++;
        }
    }
    //做一遍01背包
    for(int i = 1; i < cnt; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if(j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
        }
    }
    cout << f[cnt - 1][m] << endl;
    return 0;
}
//这里利用常见的空间优化手段进行代码书写
//当然大家可以直接用一维的01背包模板去套
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 11005, M = 2005; 
int f[2][M];
int w[N], v[N];

int main() {
    int n, m;
    cin >> n >> m;
    int cnt = 1;
    for(int i = 1; i <= n; i ++ ) {
        int ww, vv, ss;
        cin >> ww >> vv >> ss;
        int flag = 1;
        while(ss - flag >= 0) {
            w[cnt] = ww * flag;
            v[cnt] = vv * flag;
            ss -= flag;
            flag *= 2;
            cnt ++ ;
        }
        if(ss) {
            w[cnt] = ww * ss;
            v[cnt] = vv * ss;
            cnt ++;
        }
    }
    //做一遍01背包
    for(int i = 1; i < cnt; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i & 1][j] = f[i - 1 & 1][j];
            if(j >= w[i]) f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - w[i]] + v[i]);
        }
    }
    cout << f[cnt - 1 & 1][m] << endl;
    return 0;
}

(5)单调队列优化

证明：

对于我们的二进制的优化，我们发现，我们只是把原本的东西扁平化处理了，但是最终还是要处理大量的数据。如果当我们的n和m稍微再大一些 ，那么我们用二进制优化，发现也是过不去的。那么这个时候我们可以想一下怎么继续减少我们的时间。我们发现遍历物品的那一层循环n是肯定优化不掉了，那么我们就需要考虑再推导我们的f数组的时候，能否把我们的f数组推导过程变成线性的。

然后我们再次看一下如果我们是简单的多重背包解法的推导式子：
$$
f[i][j]=max\begin{cases}f[i-1][j], 不选择i这些物品 \\f[i-1][j-kw[i]]+kv[i], 选择k个i物品且1\le k\le s[i]&& (j-kw[i])>=0\end{cases}
$$
看着这个式子之后，我们先举一个例子。

假设我们背包的整个容量为10，而当前我们递推到了第i个物品，这个物品的体积为2，价值为2，数量为3。通过这个例子我们代入我们上面的推导式子我们可以发现下面的一个规律。

• $f[10]$只是由我们的$f[8], f[6],f[10]$推导而来
• $f[9]$只是由我们的$f[7], f[5],f[3]$推导而来
• $f[8]$只是由我们的$f[6], f[4],f[2]$推导而来
• ·········································································
• $f[2]$只是由我们的$f[0]$推导而来

我们可以看到假设我们的体积为w的话，那么一个数是由比他小，且小的那些数和这个数构成了等差数列，并且等差数列的公差恰好就是为我们的w。而这样的一个性质可以那么解释，假设当前我们推导的是f[i],那么能够有机会推导出$f[i]$的其他下标我们记作$idx$,所以必定会有$idx%w==i%v$  ,也就是说这些数必须模上当前的体积w同余！

有了上面的性质我们再进一步的去看一下，怎么让我们在每一次推导都是线性的呢?

由于每一个推导出来的数%w都是同余的才能进行，那么我们不妨以%w的余数作为推导的一整套流线。比如以上面w为2，那么我们就以模上w为0或者1，把所有10的状态分为下面的两种状态。

• 0,2,4,6,8,10
• 1,3,5,7,9

那么我们在推导的时候只需要关注组内之间的状态就好了。有了上面的铺垫之后，加上对于数量的限制，我们的问题就变成了。

如何快速求出一个窗口的最大值？

为什么变成了这个问题呢?通过上面的例子看出，每一组内还有一个数量限制，比如我们开头的数量为3，那么推6的时候，其实就是求前三个数中的0,2,4哪一个状态贡献给6的价值会是最大的。也就是说此时我们要求出一个窗口大小的最大值固定好了的一个滑动窗口的最大值！

至此我们终于知道，oh原来这里是一个滑动窗口的题目！那么至于滑动窗口线性解决的方法就锁定到了我们这里最开始讲到的单调队列！！

而对于单调队列去维护一个窗口的最大值，无疑就是锁定两个点:

• 什么情况对头会被弹出？
• 什么情况队尾会被新值更新？

1.什么情况对头会被弹出？

这里很好想，我们发现，每个数i最多只能由前面三个数来推导，因为我们规定了一个组的数量只能为3，也就是我们最多选3个物品。也就是当物品数量为s的时候，我们只能由同组内，目前下标为i，在i前最多存在s个状态。用代码来表示就是说$(i-q[对头])/w \le s$,举个例子，假设我们现在推导到的下标为8，如果队列还存在0，2，4，6的话，那么$(8-0)/2=4\gt3$,所以我们的对头0就必须出队，因为他已经不在我们的窗口内了！

2.什么情况队尾会被新值更新？

这个地方是需要一个推导的。我们发现，如果当前我们推导到的元素，他贡献的效果比之前队列队尾的贡献的更好的话。我们就需要让队尾出队。那么这个贡献应该怎么算呢?还是以上面为例子。如果我们当前推导到的下标为6了。那么假设前3个元素都还在队列的话，那么会有。
$$
f[6]=max\begin{cases}
f[0]+3v(v表示这个物品的价值) \\
f[2]+2v \\
f[4]+v
\end{cases}
$$
那么假设4对后面的贡献比6对后面的贡献要小，那么4应该出队，但是，推导的时候，后面加的数量*价值是不一样的，我们怎么判断哪个的价值更高呢？很简单，我们只需要把这个贡献的影响消掉就好了。怎么消掉呢?

假设我们后面推导的是8,那么对于前面存在可能有6和4的贡献，即有
$$
f[8]=max\begin{cases}
f[4]+2v \\
f[6]+v
\end{cases}
$$
也就是我们要证明出来$f[6] >= f[4]+v$,那么同理，如果我们的6比2的贡献也大的话，我们就需要证明$f[6]>=f[2]+2v$,而我们发现在v前面的这个系数，刚好和我们推导的两个数的下标有关系，正如:
$$
1(*v)=(6-4)/2 \\
2(*v)=(6-2)/2
$$
也就是，我们去对比当前下标产生的价值是否是队尾下标产生的价值加上他们的一个差值量价值，而这个差值量价值刚好就等于我们两个下标的差值除以体积。

那么用式子表示是什么样的呢？假设当前推到的下标为k, 当前队尾元素的下标为q[tt], 当前物品的体积为w，价值为v那么如果要出队就需要满足下面的式子:
$$
hh <= tt(队列中存在元素) \\
g[k] >= g[q[tt]] + (k - q[tt]) / w * v
$$
至此，我们完美收官我们的推导过程！！！

时间复杂度： $O(n*m)$

完整AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 20050;
//f代表动态规划数组，q代表优先队列
//g复制上一层的f数组避免当前f数组如果更新，就会影响贡献值的判断
int f[N], q[N], g[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) {
        int w, v, s;
        cin >> w >> v >> s;
        //先枚举我们的余数,余数不会大于等于体积w,否则于之前的于数等价
        for(int j = 0; j < w; j ++ ) {
            memcpy(g, f, sizeof f);
            //给出队列的对头和队尾初始值
            //队列存的是0-m的下标
            int hh = 0, tt = -1;
            //开始从余数依次枚举，数依次为k, 2 * k, ...;
            //k表示当前循环找到的下标
            for(int k = j; k <= m; k += w) {
                //判断对头是否越界，越界就出队
                if(hh <= tt && (k - q[hh]) / w > s) hh ++ ;
                //如果对头存在，利用对头更新我们的结果
                if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / w * v);
                //如果当前比队尾更优，队尾出队
                while(hh <= tt && g[k] >= g[q[tt]] + (k - q[tt]) / w * v) tt -- ;
                //当然有下面这一种写法也是对的，其实都是在求一个相对值
                //while(hh <= tt && g[k] - (k - j) / w * v >= g[q[tt]] - (q[tt] - j) / w * v) tt -- ;
                
                //当前元素下标入队
                q[++ tt ] = k;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

---

④ACwing.9分组背包

(1)题目描述

(2)dp分析

这题其实就是多重背包的一个扩展，只不过每一组内的背包体重和价值都不同了而已。而且由于每一组只能选择一个物品，那么其实也是01背包的扩展，包括多重背包优化后也是算01背包的扩展。

状态转移方程
$$
f[i][j]=max\begin{cases}
f[i-1][j], 不选择第i组的这些物品 \\
f[i-1][j-w[i][k]]+v[i][k],选择i组的第k个物品
\end{cases}
$$

(3)完整AC代码

//不进行空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int f[N][N], s[N];
int w[N][N], v[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) {
        cin >> s[i];
        
        for(int j = 1; j <= s[i]; j ++ ) cin >> w[i][j] >> v[i][j];
    }
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            for(int k = 0; k <= s[i]; k ++ ) {
                if(j >= w[i][k]) {
                    f[i][j] = max(f[i][j], f[i - 1][j - w[i][k]] + v[i][k]);
                }
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}
//进行空间优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int f[2][N], s[N];
int w[N][N], v[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) {
        cin >> s[i];
        
        for(int j = 1; j <= s[i]; j ++ ) cin >> w[i][j] >> v[i][j];
    }
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i & 1][j] = f[i - 1 & 1][j];
            for(int k = 0; k <= s[i]; k ++ ) {
                if(j >= w[i][k]) {
                    f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - w[i][k]] + v[i][k]);
                }
            }
        }
    }
    
    cout << f[n & 1][m] << endl;
    
    return 0;
}