5.背包问题

在动态规划问题中，有一个非常经典的问题：给定 $n$ 个物品，每个物品都有它的重量 $w_i$ 和价值 $v_i$，给定限重，求获得的最大价值。比如说，如果有三个物品，重量分别为 $3,4,5$，价值都是 $1$，限重为 $7$，那么显然获得的最大价值就是 $2$。现在我们来基于这个问题进行讨论。

5.1. 0/1背包

0/1背包的具体意思是，对于每个物品，你只能选择拿/不拿，不拿代表 $0$，拿代表 $1$，故称作“0/1背包”。

那这个问题如何解决呢？我们可以设 $f_{i,j}$ 表示从前 $i$ 个物品，限重为 $j$ 时所获得的最大价值。考虑第 $i$ 个物品，如果拿，那么价值就是 $f_{i-1,j-w_i}+v_i$；若否，就是 $f_{i-1,j}$。进而得到状态转移方程：

$f_{i,j}=\text{max}\{f_{i-1,j-w_i}+v_i,f_{i-1,j}\}$

时间和空间复杂度都是 $O(n^2)$。

可以再想一想，有没有空间上更加优化的方法呢？注意到优化空间的方法有降维法，所以关注第二维，即为

$f_j=\text{max}\{f_{j-w_i}+v_i,f_j\}$

但是很容易想到，如果 $f_{j-w_i}$ 比 $f_j$ 预先处理了，那么 $f_j$ 的下一步更新就会发生错误。所以我们要进行倒序更新。

具体代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;//n为物品数，m为限重
struct Node{
    int w;//重量
    int v;//价值
}a[1005];//物品的信息
int f[1005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].v);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i].w;j--)//倒序处理
            f[j]=max(f[j],f[j-a[i].w]+a[i].v);
    printf("%d\n",f[m]);//最后输出容量至多为m的最大获得价值，即f[m]
    return 0;
}

在普及组（CSP-J）竞赛中，背包问题还是比较常见的。而最致命的错误就是将 $j$ 的循环顺序写为正序。你可能会好奇：如果将其写为正序，会有什么样的后果呢？

5.2. 完全背包

如果有三个物品，重量分别是 $3,4,5$，价值都是 $1$，限重 $9$。本来答案应该是 $2$，但是当你将循环顺序写成正序的话，就发现答案变成了 $3$。

你想到了什么？程序将第一个物品用了三遍！

当你再次尝试限重是 $12,15$，甚至是 $300$ 时，你会发现程序在不断地使用第一个物品。这就是我们的完全背包：所有物品可以使用无限多次。

再仔细思考一下为什么正序遍历会变成完全背包。如果将 $f_j$ 更新为 $f_{j-w_i}+v_i$，就相当于在背包中加入了物品 $i$。我们之所以倒序遍历，是为了避免更新完 $f_j$ 又更新 $f_{j+w_i}$，也就是说物品 $i$ 放了多于一次。这不就是完全背包所需要的条件吗！

好了，分析到这里，完全背包的代码也就出来了。只需要将倒序改为正序即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;//n为物品数，m为限重
struct Node{
    int w;//重量
    int v;//价值
}a[1005];//物品的信息
int f[1005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].v);
    for(int i=1;i<=n;i++)
        for(int j=a[i].w;j<=m;j++)//正序处理
            f[j]=max(f[j],f[j-a[i].w]+a[i].v);
    printf("%d\n",f[m]);//最后输出容量至多为m的最大获得价值，即f[m]
}

5.3.多重背包

其实，完全背包在生活中的应用并不是很广。有什么物品能保证供应无限呢？每个物品其实都有它的限量，也就是最多能装多少。这就是多重背包的定义。

我们把每种物品都加上一个限量 $m_i$，表示这个物品最多装 $m_i$ 个。那么这种情况下如何求最大价值呢？我们仍然定义 $f_{i,j}$ 为前 $i$ 个物品，限重为 $j$ 时所获最大价值。因为 $i$ 物品可以选 $0-m_i$ 个，那么就有：

$f_{i,j}=\max\{f_{i-1,j-k\times w_i}+k\times v_i\}$

其中 $k=0,...,m_i$，分别表示选 $0-m_i$ 个物品。时间复杂度 $O(n^3)$，显然太大了。

那如何进行优化呢？可以考虑将多重背包转化为0/1背包。很容易想到，将第 $i$ 个物品分成 $m_i$ 个物品，每种物品选择拿/不拿，就变成了0/1背包了。但是这样的时间复杂度仍然为 $O(n^3)$，怎么办？

有什么方法可以用很少的数表示更大的数呢？很显然是二进制。比如说，如果 $m_i=7$，那么我们将其拆分成三个物品，第一个物品的重量和价值是原来的 $4$ 倍，第二个物品是原来的 $2$ 倍，第三个物品是原来的 $1$ 倍。这样就可以不用拆为 $7$ 个物品，仅需 $3$ 个物品就可以做到转化为0/1背包。

每一个物品拆分的个数都是 $O(\log n)$ 级别的，所以说总体时间复杂度 $O(n^2\log n)$，非常优秀。我们以P1776 宝物筛选为例子写代码。

#include<bits/stdc++.h>
using namespace std;
const int N=10005,W=40005;
int n,w;//n表示物品个数，w表示限重
struct Node{
	int val;//价值
	int cost;//重量
}a[N];//每个物品的信息
int tot=0;//用于记录拆分物品的个数
int f[W];
int ans=0;//答案
int main(){
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++){
		int v,co,sum;
		scanf("%d%d%d",&v,&co,&sum);
        //二进制拆分
		for(int j=1;j<=sum;j*=2){
			a[++tot].val=v*j;//拆分成重量和价值为原来的j倍
			a[tot].cost=co*j;
			sum-=j;//记录还剩多少
		}
		if(sum)//如果还剩下一些东西，那么就再分出来一个物品
		a[++tot].val=v*sum,
		a[tot].cost=co*sum;
	}
    //最后进行0/1背包即可
	for(int i=1;i<=tot;i++)
		for(int j=w;j>=a[i].cost;j--)
			f[j]=max(f[j],f[j-a[i].cost]+a[i].val);
	printf("%d\n",f[w]);
}

5.4. 混合背包

学完了三种背包，自然就会想：如果物品中有的是有限量的，有的则没有限量，那么怎么求最大价值？

很自然地想到，对于有限制的物品，先将其二进制拆分为0/1背包。然后就是0/1背包和完全背包的混用了。在进行第二次循环之前，判断这个物品是否是0/1背包，如果是则倒序循环，否则就正序循环。

5.5. 二维背包

在做一件事情时，你需要考虑两种成本：金钱成本 $a_i$ 和时间成本 $b_i$。这样的话，花费就是二维的，如何处理最大价值呢？

令 $f_{i,j,k}$ 为前 $i$ 个物品，金钱成本不超过 $j$，时间成本不超过 $k$ 所获得的最大价值。那么：

$f_{i,j,k}=\max\{f_{i-1,j,k},f_{i-1,j-a_i,k-b_i}+v_i\}$

考虑优化，可以去掉第一维，对剩下两维进行倒序遍历则为0/1背包，正序遍历则为完全背包。

5.6. 分组背包

有的时候，一些时间不能同时进行。比如，你在看电影时，就不能同时帮妈妈打扫卫生。这就引出了分组背包问题：物品被分为若干组，每一组的物品互相冲突，最多选一种。求最大价值。

这也比较简单：令 $f_{i,j}$ 表示前 $i$ 组物品，限重为 $j$ 所获得的最大价值。那么：

$f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-w_k}+v_k\}$

其中 $k$ 在第 $i$ 组中。时间复杂度为 $O(n^2)$，因为枚举 $i,k$ 的总体复杂度是 $O(n)$ 而并不是 $O(n^2)$。

5.7. 背包方案总数

上述的问题都是让你求最好方案下的答案。那么还有一类题，需要让你求在装特定的重量下，有多少种可能性。设 $f_{i,j}$ 为前 $i$ 个物品，装的重量为 $j$ 的方案数。那么：

$f_{i,j}=f_{i-1,j}+f_{i-1,j-w_i}$

初始化 $f_{0,0}=1$。

5.8. 练习题

P1616 疯狂的采药
P1510 精卫填海
【2019CSP-J第三题】P5662 纪念品
【USACO2009二月金组】P2938 Stock Market