背包问题

本讲前言

对于任何一题 DP 题，我们都可以按照以上方法去思考，对于状态计算中集合的划分，遵循以下原则：

1. 不重不漏，不重有特例，有些时候可以重复。

2. 将集合划分为更小的子集，假设之前的状态已经算出，推导所有子集。

3. 初始状态必须明确

目前考试很注重DP的优化，优化无非就是对集合的划分的优化，通俗点说，就是对状态转移的优化。

在分析一题DP题的时候，我们先考虑如何来表示状态，一般情况下可以从题目、过往经验入手，即题目是一道DP裸题，或者是我们学过的某种DP的变形，一般情况下都是后者，这时我们对于状态表示中的集合就可以通过已有模型去替换。这是非常重要的一点，因为我们去思考DP题目的时候，如果不通过已有模型进一步思考，就会比较难想到表示方法。

我们在现阶段主要学习背包问题、最长上升子序列、线性DP、区间DP、计数类DP、数位统计DP、状压DP以及树形DP的经典模型题。以充足“储备”。

所以现阶段目标是把十八题例题完全吃透、弄懂。

之后的学习中（四阶段），我们再继续深入的剖析动态规划。

经典例题

例题 01背包问题 J31501

问题描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

数据范围：$0<N,V\le 10000<v_i,w_i\le 1000$

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

题目分析

01背包问题是比较简单的动态规划问题，也是其余背包问题的基础，基本上所有的背包问题都是从01背包发展而来，所以弄懂01背包问题既是学习背包问题的基础，也是重点。

我们都知道，动态规划是不断决策去求最优解的过程，01背包即是不断对第 $i$ 个物品做出决策，$0$ 和 $1$ 代表的不选或选。

由此我们可以推断出： 状态表示：$f[i][j]$

• 集合：只从前 $i$ 个物品中选，体积不超过j的所有选法的集合。

• 属性：最大值。

状态计算：

• 不选第i个物品：意味着$f[i][j]=f[i-1][j]$，此公式的含义是，不选第 $i$ 个物品，那么从前 $i-1$ 个物品中选体积不超过 $j$ 的最大值。

• 选第 $i$ 个物品：意味着 $f[i][j]=f[i-1][j-v[i]]+w[i]$，此公式的含义是，选第 $i$ 个物品，那么在选好了前 $i-1$ 个物品的情况下，留出 $v[i]$ 的空间（即 $j-v[i]$ ）给 $i$ 物品，再加上第 $i$ 个物品的价值 $w[i]$ 即可。

• 那么选和不选中选择最大值就是我们 $f[i][j]$ 的值，统一后公式为：$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]$

• 初始状态：$f[1...n][0]=0$，即体积为0时，不管选什么物品，最大价值都为0。

示例代码一

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N];
int n, m;

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

优化空间：

通过代码我们发现，$f[i][j]$ 中的第一维只用到了 $i-1$ 以及 $i$ 两个，所以可以考虑进行优化空间，那么需要用一个数组来记录 $i-1$ 的状态吗？

其实是不需要的，因为 $f[i][j]$ 的值来源是 $f[i-1][0...j]$，所以只要我们能用到 $[0...j]$ 中的值即可，那么有一个很巧妙的优化方法：因为 $j$ 和 $j-v[i]$ 都是小于等于$j$的，我们可以使得 $j$ 从大往小枚举，这样先用到的 $j$ 就是上一层（$i-1$）的 $j$ 了。

示例代码二

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N], v, w;
int n, m;

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

代码中的 $f$ 数组也称之为滚动数组。

例题 完全背包问题 J31502

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i$，用空格隔开，分别表示第 $i$ 种物品的体积和价值。

数据范围：$0<N,V\le 1000$，$0<v_i,w_i\le 1000$

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

题目分析

我们目前已经学习了 $01$ 背包问题，那么从 $01$ 背包问题思路角度，如何去完成完全背包问题呢？

完全背包和 $01$ 背包的不同之处在于，物品的数量是无限的，值得注意的是，物品数量虽然无限，但是背包容量是有限的，从而推断出每个物品其实是有上限的，我们称之为 $x_i$，即物品 $i$ 最多取 $x$ 个就存不下了。

可以画个图理解一下：

即对于前 $i$ 个物品，体积不超过 $j$ 的情况下，我们物品 $i$，可以取 $0$ 个，$1$个，...，$x_i$个，结合 $01$ 背包的代码，我们可以很轻松的写出一下代码：

#include<iostream>
using namespace std;

const int N = 1010;

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

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ ) //k个表示物品i的个数
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);//求出每一个 f[i][j]
    cout << f[n][m] << endl;
}

此代码在 $01$ 背包问题的基础上，增加了取 $2$ 个 ... 取 $x_i$ 个的枚举情况，显然是正确的。

但是，此代码时间复杂度为 $O(n{m}^2)$，会超时，那么我需要优化。

优化过程如下：

$f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i,f(i-1,j-2v_i)+2w....)$

$f(i,j-v_i)=max(f(i-1,j-v_i),f(i-1,j-2v_i)+w....)$

可以发现，第二个式子相当于第一个式子除第一项之外的后面的项，只是少加了一个$w_i$而已

那么$f(i,j)=max(f(i-1,j),f(i,j-v_i)+w_i)$

我们再来回忆一下 $01$ 背包的状态转移方程：

$f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i)$

可以发现，$01$ 背包问题是从 $i-1$ 状态转移而来，而完全背包是从第 $i$ 层状态转移而来。

更通俗的理解是，我们在考虑第 $i$ 个物品时，先假设现在取 $0$ 个，那么后续的无论取多少个，都是从取 $0$ 层状态而来，即本层。

综上分析，我们可以总结为：

状态表示

• 集合
  • 只从前 $i$ 个物品中选，体积不超过 $j$ 的所有选法的集合。
• 属性
  • 最大值。

状态计算

• 集合划分
  • 选 $0$ 个
  • 选 $1$ 个
  • ...
  • 选 $x_i$ 个
• 状态转移方程
  • $f[i][j]=max(f[i-1][j],f[i][j-v_i]+w_i)$

所以我们可以写出如下代码：时间复杂度 $O(nm)$

示例代码

#include<iostream>
using namespace std;

const int N = 1010;

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

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

同样的，我们依旧可以变成滚动数组，和 $01$ 背包不同的是，$01$ 背包是从上层而来，我们必须保留小的以利用上一层的数据，所以第二层循环必须倒着来，而完全背包是从本层状态转移而来，所以必须先更新小的，这样才能利用到本层计算过的状态。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010;
int f[N];
int v, w; 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin >> v >> w;
		for(int j = v; j <= m; j++)
            f[j] = max(f[j], f[j-v] + w);
	}	
	cout << f[m] << endl;
}

至此，我们已经分析完了完全背包问题。

分析简图如下：

例题 多重背包问题I J31503

问题描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

数据范围：$0<N,V\le 100$，$0<v_i,w_i,s_i\le 100$

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例

10

题目分析

本题和 $01$ 背包相比，第 $i$ 个物品的数量是固定的，数据范围较小。我们可以结合完全背包的第一个思路，直接枚举第 $i$ 个物品取多少个，算出最后结果。

代码如下：时间复杂度$O(nms)$

/*多重背包问题1*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 20;
int v[N], w[N], s[N];
int n, m;
int f[N][N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++) //直接枚举数量
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
            
    cout << f[n][m] << endl;        
            
}

例题 多重背包问题II J31504

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

数据范围：$0<N\le 1000$，$0<V\le 2000$，$0<v_i,w_i,s_i\le 2000$

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例

10

题目分析

本题和例题三相比，数据范围更大了，同样的做法会超时，所以我们需要进行优化，这里介绍一个常见优化技巧：二进制优化。

考虑思路：对于第 $i$ 个物品，我们可以对其进行打包：打包 $1$ 个，$2$ 个，$4$ 个，....,$2^{k_i}$ 个，这样，每种物品都被打包成了 $k_i$ 个物品，这样，就变成了 $01$ 背包问题了，总物品数量从 $n$ 个变成了 $log(s_1)+log(s_2)+...+log(s_n)$ ，每个物品最多 $2000$ 个，最多打包成$log(2000)$，大约是 $10$ 个左右，总物品数量为 $10000$ 个，总时间复杂度为 $O(10000m)$，其中 $m$ 为背包总体积。

示例代码

/*多重背包问题2*/
#include<bits/stdc++.h>
using namespace std;
const int N = 15000, M = 2020;
int w[N], v[N], f[M];
int n, m;
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s) //打包
        {
            cnt ++;
            v[cnt] = a * k; 
            w[cnt] = b * k;
            s -= k;
            k <<= 1;
        }
        if(s > 0) //如果最后还有剩余，额外打包一次，因为不能保证一定能完整打包
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;
    
}

这就是多重背包的二进制优化。

当然，多重背包还有更加高效的优化方式，即单调队列优化方式，这个方法我们将在之后的学习中继续学习。

例题 分组背包问题 J31505

问题描述

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 $N，V$，用空格隔开，分别表示物品组数和背包容量。

接下来有 $N$ 组数据：

• 每组数据第一行有一个整数 $S_i$，表示第 $i$ 个物品组的物品数量；
• 每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij},w_{ij}$，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

数据范围：$0<N,V\le 100$，$0<S_i\le 100$，$0<v_{ij},w_{ij}\le 100$

输出格式

输出一个整数，表示最大价值。

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例

8

题目分析

本题和 $01$ 背包问题相比，仅仅是多了一个限制，即第 $i$ 个物品变成了第 $i$ 组物品，但是因为每组物品只能选一个，所以本质上还是 $01$ 背包问题，我们只需要考虑每组物品选哪一个就行了，即枚举每一个物品。

示例代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int N = 110;  
int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值  
int v[N][N], w[N][N], s[N]; //v为体积，w为价值，s代表第i组物品的个数  
int n, m, k;  
  
int main() {  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) {  
        cin >> s[i];  
        for (int j = 0; j < s[i]; j++) {  
            cin >> v[i][j] >> w[i][j]; //读入  
        }  
    }  
  
    for (int i = 1; i <= n; i++) {  
        for (int j = 0; j <= m; j++) {  
            f[i][j] = f[i - 1][j]; //不选  
            for (int k = 0; k < s[i]; k++) {  
                if (j >= v[i][k])  
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);  
            }  
        }  
    }  
    cout << f[n][m] << endl;  
}

本题也可以使用滚动数组进行优化：

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

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

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

再次深入思考一下，有没有什么办法可以继续剩下多出的二维数组的空间呢，其实可以的，我们可以边输入边处理，那么会遇到的问题有两个。

第一个问题：代码中的 $k$ 枚举了第 $i$ 组的所有物品，如果不提前输入，就没办法使用，那么我们可以考虑先进行第 $i$ 组第 $k$ 个物品，再枚举体积，即把第二个循环和第三个循环对换。

由此，又会产生第二个问题：对于某一个物品，会更新掉 $f$ 数组的值，这样下一个物品使用的就不会是第 $i-1$ 层的状态了，如何解决呢，可以想到复制一遍第 $i-1$ 层的状态。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int M = 110;
int f[M], last[M];
int n, m, s, v, w;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < s; j++) {
            cin >> v >> w;
            for (int k = m; k >= v; k--)
                f[k] = max(f[k], last[k - v] + w);
        }
        memcpy(last, f, sizeof f); //复制一份，保证使用第i-1层状态
    }
    cout << f[m] << endl;

    return 0;
}

至此，空间优化成了$O(n)$