分享
DP 背包讲义
root LV27 至高道祖 LV 2 SU @ 2024-7-26 9:24:15

背包问题

本讲前言

Pasted image 20240318151433.png

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

不重不漏，不重有特例，有些时候可以重复。
将集合划分为更小的子集，假设之前的状态已经算出，推导所有子集。
初始状态必须明确

目前考试很注重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 \lt N, V \le 1000 0\lt v_i, w_i \le 1000$

输出格式

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

输入样例

输出样例

题目分析

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

[!QUESTION] 这里略微思考下暴力的做法：每个物品都有选和不选两种决策， $N$ 个物品，总共需要枚举 $2^N$ 种情况，故会超时。而动态规划是利用已经求过值来求未知，减少枚举次数。

我们都知道，动态规划是不断决策去求最优解的过程，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。

Pasted image 20240315143648.png

Pasted image 20240318151149.png

示例代码一

#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 \lt N, V \le 1000$ ， $0 \lt v_i, w_i \le 1000$

输出格式

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

输入样例

输出样例

题目分析

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

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

可以画个图理解一下：

Pasted image 20240318140639.png

即对于前 $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(nm^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;
}

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

分析简图如下：

Pasted image 20240318142332.png

例题多重背包问题I J31503

问题描述

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

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

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

输入格式

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

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

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

输出格式

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

输入样例

输出样例

题目分析

本题和 $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 \lt N \le 1000$ ， $0 \lt V \le 2000$ ， $0 \lt v_i, w_i, s_i \le 2000$

输出格式

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

输入样例

输出样例

题目分析

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

考虑思路：对于第 $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 \lt N, V \le 100$ ， $0 \lt S_i \le 100$ ， $0 \lt v_{ij}, w_{ij} \le 100$

输出格式

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

输入样例

输出样例

题目分析

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

Pasted image 20240318145004.png

示例代码

#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)$

目前还没有评论...

DP 背包讲义

背包问题

本讲前言

经典例题

例题 01背包问题 J31501

问题描述

输入格式

输出格式

输入样例

输出样例

题目分析

示例代码一

示例代码二

例题 完全背包问题 J31502

题目描述

输入格式

输出格式

输入样例

输出样例

题目分析

示例代码

例题 多重背包问题I J31503

问题描述

输入格式

输出格式

输入样例

输出样例

题目分析

例题 多重背包问题II J31504

题目描述

输入格式

输出格式

输入样例

输出样例

题目分析

示例代码

例题 分组背包问题 J31505

问题描述

输入格式

输出格式

输入样例

输出样例

题目分析

示例代码

0 条评论

状态

开发

支持

关于

登录

例题完全背包问题 J31502

例题多重背包问题I J31503

例题多重背包问题II J31504

例题分组背包问题 J31505