背包问题

背包问题是一个经典的动态规划的问题，大致是给定一个背包的容量与一些物品的重量和价值。要求在物品总重量总和不超过背包容量的前提下，使所得物品总价值最大。

背包问题大致分为以下几种类型：01 背包、完全背包、多重背包、分组背包等。

01 背包

01 背包问题是背包问题中最基础，也是最简单的一类问题。它的主要特点为：对于每个物品，要么选，要么不选。因此被称为 01 背包。

经典问题如下：

有

n

种物品要放到一个袋子里，袋子的总容量为

m

，第

i

种物品的体积为

v_i

，把它放进袋子里会获得

w_i

的收益，每种物品只能用一次，问如何选择物品，使得在物品的总体积不超过

m

的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

方法 1——枚举（暴搜）

写一个深搜程序，对

n

个物品分别进行选与不选的枚举（大致代码如下），时间复杂度为

O(2^n)

。

CPP

int ans = 0;
void dfs(int i,int vsum,int wsum){
    // i -> 搜索到第 i 个物品  vsum,wsum -> 分别为目前已选物品的体积、价值之和
    if (i == n + 1){
        if (vsum <= m) ans = max(ans,wsum);
        return;
    }
    if (v[i] + vsum <= m) dfs(i+1,vsum+v[i],wsum+w[i]); //选
    dfs(i+1,vsum,wsum); // 不选
}

方法 2——

当我们考虑了前

i

个物品选或不选，如果有两组方案的总体积是一样的，那么我们只需要保留总收益大的那组。把考虑了前

i

个物品以后，总体积为

0,1,...,m

时的最大收益都记下来。所以，我们可设

dp_{i,j}

表示考虑前 $i$ 个物品，在背包容量为 $j$ 时，所能获得的最大价值。

考虑前

i

个物品，总体积为

j

时存在两种情况：

不选第 $i$ 个物品，问题就变成了考虑前 $i-1$ 个物品总体积为 $j$ 的情况；
选第 $i$ 个物品，问题就变成了考虑前 $i-1$ 个物品总体积为 $j-v_i$ 的情况。

综上所述：可得状态转移方程式：

dp_{i,j} = \max(dp_{i-1,j},dp_{i-1,j-v_i} + w_i)

写出代码：

CPP

int dp[N][M]; //其中N和M分别代表n和m的最大值

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        if (j < v[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
    }
}

但是，这样的代码过于复杂，我们可以用以下几个技巧优化，同时，这些技巧是动态规划的常用优化技巧，第一个特别常用！！！

技巧 1——滚动数组

注意到上面代码的空间复杂度为

O(NM)

，很明显，在很多题目都会被卡掉，于是，我们需要思考一个问题：需不需要开这么大的数组？

再看到代码，发现考虑前

i

个物品时的状态只和考虑了前

i-1

个物品时的状态有关，所以前面

i-2

行的数据是不用储存的！！！

因此，我们可以使用滚动数组。对于本题，可以使用以下两种方法：

CPP

//方法一：

int f[M],g[M];
// f 数组代表前 i-1 个物品的状态
// g 数组代表前 i 个物品的状态

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        if (j < v[i]) g[j] = f[j]; //注意中括号内的变量！！！
        else g[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    memcpy(f,g,sizeof(g)); // 将 g 复制一份给 f
}
cout << f[m]; // 等价于：cout << g[m]

CPP

// 方法二：

int dp[2][M];
for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        if (j < v[i]) dp[(i)&1][j] = dp[(i-1)&1][j];
        else dp[i&1][j] = max(dp[(i-1)&1][j],dp[(i-1)&1][j-v[i]]+w[i]);
    }
}
cout << dp[n&1][m];

一般来讲，第二种会更加常用，也更加好用。

技巧 2——逆序滚动数组

先看代码：

CPP

int dp[M];
for (int i=1;i<=n;++i){
    for (int j=m;j>=a[i];--j){
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

来解释一下原因：（为区分滚动数组优化和逆序滚动数组优化的代码区别，滚动数组优化中的

dp

数组在下文改为

f

数组）

如图，红底和蓝底部分表示目前

dp

数组内，当用二维数组表示时对应的位置。假设现在倒序遍历到蓝底位置，且

v_i

为

2

。根据之前的代码，应该算出

f_{i-1,j}

和

f_{i-1,j-v_i} + w_i

，在新的代码中却是使用了

dp_j

和

dp_{j-v_i}+w_i

，因此，只需判断他们等不等价，就能知道新代码是否正确。

先看

f_{i-1,j}

和

dp_j

，因为刚好遍历到

j

为

3

的位置，因此

dp_3

还未更新，所以

dp_3

储存的值不变，也就是等于绿底，为

f_{i-1,3}

。所以，

f_{i-1,j}

等价于

dp_j

。

再看

f_{i-1,j-v_i} + w_i

和

dp_{j-v_i}+w_i

，因为

w_i

相同，所以对比

f_{i-1,j-v_i}

和

dp_{j-v_i}

。因为

j=3

所以

j-v_i

得到的数一定小于等于

3

，即一定在绿底左边的红底的一位置，而这些位置代表的是

f_{i-1,j}

，所以

f_{i-1,j-v_i} + w_i

等价于

dp_{j-v_i}+w_i

。

综上所述：两段代码等价。（后面的代码基本会也只会使用这种写法）

这样，01背包的状态转移方程式就可以变为（一定要注意，这里是逆序！）

dp_j = \max(dp_j,dp_{j-v_i}+w_i)

模板题

P1048 采药

需要注意的是：这道题目的

n

和

m

，是反着输入的！

正确代码：

CPP

#include <bits/stdc++.h>
#define N 105
#define M 1005
using namespace std;

int n,m;
int w[105],v[105];
int [1005];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> m >> n;
	for (int i=1;i<=n;++i) cin >> w[i] >> v[i];
	for (int i=1;i<=n;++i){
		for (int j=m;j>=w[i];--j){
			[j] = max([j],[j-w[i]]+v[i]);
		}
	}
	cout << [m];
	
	
	
	return 0;
}

完全背包

完全背包是背包问题的另一种问题，区别于01背包，完全背包的特点是：对于每种物品，可以取任意件。

经典问题如下：

有

n

种物品要放到一个袋子里，袋子的总容量为

m

，第

i

种物品的体积为

v_i

，把它放进袋子里会获得

w_i

的收益，每种物品能用无限次，问如何选择物品，使得在物品的总体积不超过

m

的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

参考01背包的做法，依旧考虑前

i

种物品，总体积为

j

时存在两种情况：

不选第 $i$ 种物品，问题就变成了考虑前 $i-1$ 种物品总体积为 $j$ 的情况；
选第 $i$ 种物品，问题就变成了考虑前 $i$ 种物品总体积为 $j-v_i$ 的情况。

综上所述：可得状态转移方程式：

dp_{i,j} = \max(dp_{i-1,j},dp_{i,j-v_i}+w_i)

所以，可以写出代码：

CPP

int dp[N][M]; 

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        if (j < v[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
    }
}

我们对代码进行优化，得到以下代码：

CPP

int dp[M]; 

for (int i=1;i<=n;++i){
    for (int j=v[i];j<=m;++j){ // 正序！！！
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

可以发现，这段代码与01背包唯一的不同只有第

4

行的循环是正序的。

根据完全背包的定义，每一种物品都可以无限地取，因此如果要选择，我们应该考虑的是前

i

种物品，因为若此时可以选择第

i

种物品，意味着之前也有可能选择过第

i

种物品。要求前

i-1

种物品总值，只需像前面一样即可，因为遍历到

j

这个点时，原来的值还没有被替换掉，因此可以得到

dp_{i-1,j}

。而若要求前

i

种物品总值，我们就不能逆序

dp

，由于没有更新，所以这样求出的是前

i-1

种物品的总值，如果想要让其在遍历到

dp_j

前更新，就需要先遍历

dp_{j-v_i}

，又因为

j-v_i \le j

，所以需要正序遍历。

这样，完全背包的状态转移方程式：（一定要注意，这里是正序！）

dp_j = \max(dp_j,dp_{j-v_i}+w_i)

模板题

P1616 疯狂的采药

这道题需要注意两个点：

这道题目的 $n$ 和 $m$ ，依旧是反着输入的！
需要使用 long long 类型，否则会爆掉！（代码中使用的是宏定义的形式）

正确代码：

CPP

#include <bits/stdc++.h>
#define int long long
#define N 10005
#define M 10000005
using namespace std;

int n,m;
int w[N],v[N];
int [M];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> m >> n;
	for (int i=1;i<=n;++i) cin >> v[i] >> w[i];
	for (int i=1;i<=n;++i){
		for (int j=v[i];j<=m;++j){
			[j] = max([j],[j-v[i]]+w[i]);
		}
	}
	cout << [m];	
	
	return 0;
}

多重背包

多重背包问题是介于 01 背包和完全背包之间的一种问题。它的主要特点是：每种物品有固定的数量限制。

经典问题如下：

有

n

种物品要放到一个袋子里，袋子的总容量为

m

，第

i

种物品的体积为

v_i

，把它放进袋子里会获得

w_i

的收益，每种物品只能不超过 $l$ 次，问如何选择物品，使得在物品的总体积不超过

m

的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

方法1：多重背包转 01 背包

由于多重背包问题中，每种物品的数量是固定的，所以，我们可以通过遍历这些数量以求出答案。代码如下：

CPP

int dp[M]; 

for (int i=1;i<=n;++i){
    for (int k=1;k<=l[i];++k){// 枚举数量限制
        for (int j=m;j>=v[i];--j){
     	   dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
  	    }
    }
}

这段代码得时间复杂度为

O(M \times \sum_{i=1}^{n} l_i)

，明显过高。

方法2：二进制优化

为了优化，我们需要用到一个数学结论。首先，先看一下这个结论的简化版：

从 $1,2,...,2^m$ 中选一些数字相加，可以得出任意 $[0,2^{m+1})$ 内的值，每个数字只能用一次。

这个结论很容易得到，可以用二进制的方法来证明：因为所有数字都为

2

的幂次，所以其二进制都可以用 "

1

" 加上任意个 "

0

" 表示，因此可以得出结论。例如：

5 = (101)_2 = (100)_2 + (1)_2

，

13 = (1101)_2 = (1000)_2 + (100)_2 + (1)_2

。

因此，对于在

[2^{k+1},2^{k+2})

内的值，我们取

2^{k+1}

后，剩下的数字在

[0,2^{k+1})

内，可以从

1,2,...,2^k

中选一些数字相加得到。也就是说任意

[0,2^{k+2})

内的值可以从

1,2,...,2^{k+1}

中选一些数字相加得到。

设

m=k+1

，可以得到对于在 $[2^{m+1},n]$ 内的值，我们取 $n-2^{m+1}+1$ 后，剩下的数字在 $[2^{m+2}-n-1,2^{m+1})$ 内，可以从 $1,2,...,2^m$ 中选一些数字相加得到。

因此，我们可以枚举

1,2,...,2^k \left(2^k \le m\right)

与

m-2^{k+1}+1

，将这个问题转换为 01 背包问题。

代码如下：

CPP

int dp[M];

for (int i=1;i<=n;++i){
    int res = l[i];
    for (int k=1;k<=res;res-=k,k*=2) // 二进制拆分
        for (int j=m;j>=v[i]*k;--j) // 01背包
            dp[j] = max(dp[j],dp[j-v[i]*k] + w[i] * k);
    for (int j=m;j>=v[i]*res;--j) // 处理剩余部分
        dp[j] = max(dp[j],dp[j-v[i]*res] + w[i]*res);
}

时间复杂度为

O(M \times \sum_{i=1}^n (\log l_i))

。

模板题

P1776 宝物筛选 - 洛谷

正确代码：

CPP

#include <bits/stdc++.h>
#define int long long
#define N 105
#define M 40005
using namespace std;

int n,m;
int dp[M];
int v[N],w[N],l[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i=1;i<=n;++i) cin >> w[i] >> v[i] >> l[i];

	for (int i=1;i<=n;++i){
    	int res = l[i];
   		for (int k=1;k<=res;res-=k,k*=2)
      	  	for (int j=m;j>=v[i]*k;--j)
     	    	dp[j] = max(dp[j],dp[j-v[i]*k] + w[i]*k);
  	  	for (int j=m;j>=v[i]*res;--j)
   	    	dp[j] = max(dp[j],dp[j-v[i]*res] + w[i]*res);
	}
	cout << dp[m];
	
	return 0;
}

分组背包

分组背包问题是背包问题的一个重要变种，它引入了物品组的概念。它的主要特点是：分组背包中的物品被划分为若干组，对于相同组物品来说，最多只能选择组内的一件物品。

经典问题如下：

有

n

个物品要放到一个袋子里，袋子的总容量为

m

，第

i

个物品属于第

a_i

组，体积为

v_i

，把它放进袋子里会获得

w_i

的收益，但每组物品只能从中选择一个，问如何选择物品，使得在物品的总体积不超过

m

的情况下，获得最大的收益，请求出最大收益。（先不考虑数据范围）

考虑前

i

组物品选择完以后，把总体积

0,1,...,m

时的最大收益记下来。

考虑前

i

组物品，总体积为

j

时有以下两种情况：

不取第 $i$ 组中的物品，问题就变成了考虑前 $i-1$ 组物品，总体积为 $j$ 时的情况；
取前 $i$ 组中的物品，枚举组中的物品 $k$ ，问题就变成了考虑前 $i-1$ 组物品，总体积为 $j-v_k$ 时的情况。

用

c_i

储存在第

i

组中的物品的编号。这样，就可以得到分组背包的状态转移方程式：

dp_{i,j} = \max(dp_{i-1,j},\max_{k \in c_i}(dp_{i-1,j-v_k}+w_k))

代码如下：

CPP

for (int i=1;i<=组数;++i){
    for (int j=0;j<=m;++j){
        dp[i][j] = dp[i-1][j];
        for (int k : c[i])
            if (v[k] <= j)
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[k]]+w[k]);
    }
}

接下来，使用滚动数组进行优化，得到代码：

CPP

int dp[M];

for (int i=1;i<=组数;++i)
    for (int j=m;j;--j)
        for (int k : c[i]) // 枚举每个组中的物品
            if (v[k] <= j)
                dp[j] = max(dp[j],dp[j-v[k]]+w[k]);

时间复杂度为

O(M \times \sum_{i=1}^{K} c_i)

。

模板题

P1757 通天之分组背包 - 洛谷

正确代码：

CPP

#include <bits/stdc++.h>
#define ll long long
#define N 1005
#define M 1005
using namespace std;

int n,m;
int v[N],w[N],a[N];
vector<int> c[N];
int dp[M];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> m >> n;
	for (int i=1;i<=n;++i){
		cin >> v[i] >> w[i] >> a[i];
		c[a[i]].push_back(i);
	}
	for (int i=1;i<=n;++i){
		for (int j=m;j;--j){
			for (int k : c[i]){
				if (v[k] <= j)
					dp[j] = max(dp[j],dp[j-v[k]]+w[k]);
			}
		}
	}
	cout << dp[m];
	
	
	return 0;
}

二维背包

二维背包是背包问题的重要扩展，它在主要特点是：在01背包的基础上增加了第二个维度的限制。不仅要考虑背包的容量限制，还要考虑另一个资源限制（如重量、体积、时间等）。

经典问题如下：

有

n

种物品要放到一个袋子里，袋子的总容量为

m

，一共有

k

点体力值。第

i

种物品的体积为

v_i

，把它放进袋子里会获得

w_i

的收益，并且消耗

t_i

点体力值，每种物品只能取一次，问如何选择物品使得在物品的总体积不超过

m

并且花费总体力不超过

k

的情况下，获得最大的收益，请求出最大收益。

这个问题其实很好思考，和01背包的做法一样，考虑前

i

个物品考虑完后，记录总体积为

0,1,...,m

与总体力为

0,1,...,k

时的最大收益。

考虑前

i

组物品，总体积为

j

，总体力为

x

时，分为两种情况：

不选第 $i$ 个物品，问题就转换成了考虑前 $i-1$ 个物品，总体积为 $j$ ，总体力为 $x$ 时的情况；
选第 $i$ 个物品，问题就转换成了考虑前 $i-1$ 个物品，总体积为 $j-v_i$ ，总体力为 $x-t_i$ 时的情况。

这样，就可以得到二维背包的状态转移方程式：

dp_{i,j,x} = \max(dp_{i-1,j,x},dp_{i-1,j-v_i,x-t_i}+w_i)

于是，可以得到代码：

CPP

int dp[N][M][K];

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        for (int x=0;x<=k;++x){
            dp[i][j][x] = dp[i-1][j][x];
            if (j >= v[i] && x >= t[i])
                dp[i][j][x] = max(dp[i][j][x],dp[i-1][j-v[i]][x-t[i]]);
        }
    }
}

接下来，使用滚动数组进行优化，得到代码：

CPP

int dp[M][K];

for (int i=1;i<=n;++i)
    for (int j=m;j>=v[i];--j) // 类似01背包
        for (int x=k;x>=t[i];--x)
            dp[j][x] = max(dp[j][x],dp[j-v[i]][x-t[i]]+w[i]);

时间复杂度为

O(NMK)

。

模板题

P1507 NASA的食物计划

正确代码：

CPP

#include <bits/stdc++.h>
#define int long long
#define N 55
#define M 405
#define K 405
using namespace std;

int H,T,n;
int v[N],t[N],w[N];
int dp[M][K];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> H >> T >> n;
	for (int i=1;i<=n;++i) cin >> v[i] >> t[i] >> w[i];
	
	for (int i=1;i<=n;++i)
	    for (int j=H;j>=v[i];--j) // 类似01背包
       		for (int x=T;x>=t[i];--x)
            	dp[j][x] = max(dp[j][x],dp[j-v[i]][x-t[i]]+w[i]);
            	
	cout << dp[H][T];
	
	return 0;
}

总结

背包问题是

dp

问题的一种类别，最基础的背包问题是 01 背包和完全背包，在这两种问题的基础上，又扩展出了多重背包、分组背包和二维背包等类别。

以下为各类背包问题的对比图：

问题类型	物品特性	核心代码	时间复杂度
01 背包	每件物品选 $0$ 或 $1$ 次	逆序循环	$O(NM)$
完全背包	物品无限供应	正序循环	$O(NM)$
多重背包	每件物品最多选 $l_i$ 次	二进制优化+01背包	$O(M \times \sum_{i=1}^n (\log l_i))$
分组背包	组内物品互斥	组→容量→组内物品循环	$O(M \times \sum_{i=1}^{K} c_i)$
二维背包	两个维度限制	双重逆序循环	$O(NMK)$

其中，二维背包又可以扩展成多维背包，有多个维度的限制，当然，时间复杂度也会增加。

背包问题

文章操作

背包问题

01 背包

方法 1——枚举（暴搜）

方法 2——

技巧 1——滚动数组

技巧 2——逆序滚动数组

模板题

P1048 采药

完全背包

模板题

P1616 疯狂的采药

推荐题目：

多重背包

方法1：多重背包转 01 背包

方法2：二进制优化

模板题

P1776 宝物筛选 - 洛谷

推荐题目：

分组背包

模板题

P1757 通天之分组背包 - 洛谷

推荐题目：

二维背包

模板题

P1507 NASA的食物计划

推荐题目：

总结

相关推荐

评论

背包问题