动态规划之背包问题
题单介绍
# 背包问题
模型回顾：若干个物品，每个物品有重量和价值，有一个背包，选择若干个物品在不超过背包容量的情况下价值最大。
### 01背包
每个物品只有两种选择,选和不选。
状态设计：$f_{i,j}$为前$i$个物品中选，且总体积不超过$j$的选法的集合
状态转移：考虑是否选择第$i$个物品，不选则为$f_{i-1,j}$，意为前$i-1$个物品选，且总体积不超过$j$
选择第$i$个物品，选了以后体积才不超过$j$，没选之前体积应该是不超过$j-v[i]$,因此由$f_{i-1,j-v_i}$转移而来。
综上$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-v_i}+w_i)$
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, W, dp[105][1005], v[105], w[105];
int main()
{
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= W; j++)
{
if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
else dp[i][j] = dp[i - 1][j];
}
}
cout << dp[n][W];
return 0;
}
```
由于转移只和$i-1$这一维有关，因此可以采用滚动数组优化。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, W, dp[2][1005], v[105], w[105];
int main()
{
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= W; j++)
{
if (j >= w[i]) dp[i & 1][j] = max(dp[i - 1 & 1][j], dp[i - 1 & 1][j - w[i]] + v[i]);
else dp[i & 1][j] = dp[i - 1 & 1][j];
}
}
cout << dp[n & 1][W];
return 0;
}
```
甚至可以直接优化掉第一维，不过注意容量循环倒着枚举，主要是我们需要用到未更新的状态来更新现有的，正着循环是用已更新的来更新未更新的，就成了将一个物品选择多次。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, W, dp[1005], v[105], w[105];
int main()
{
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = W; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[W];
return 0;
}
```
[采药](https://www.luogu.com.cn/problem/P1048)
[装箱问题](https://www.luogu.com.cn/problem/P1049)
本题求剩余最小，那就是求出占用多少体积就行，我们可以将物品的价值也等价看成体积，做$01$背包即可。
```cpp
for (int i = 1; i <= n; i++)
{
for (int j = v; j >= a[i]; j--)
{
f[j] = max(f[j], f[j - a[i]] + a[i]);
}
}
cout << v - f[v];
```
[开心的金明](https://www.luogu.com.cn/problem/P1060)
**恰好装满背包的最大价值**，对于恰好装满，我们一开始必须`memset(f, 0xc0, sizeof(f))，f[0]=0`,求最大初始化小数字，求最小初始化大数字。然后再做$01$背包即可。
**背包问题求方案数**
[[USACO2.2]集合 Subset Sums](https://www.luogu.com.cn/problem/P1466)
问题转化为有$n$个数字$1\sim n$，每个数字选或不选，问最终选出的数字和恰好是总和的一半有多少种。
首先总和不是偶数直接输出$0$
状态设计定义：$f[j]$为选出和为$j$的方案数
是偶数，考虑每个数字选和不选，不选则第$i$个，则还是$f[j]$，选了第$i$个，就可以由$j-i$加上$i$得来，因此要累加所有的$f[j-i]$的方案。
转移：$f[j] += f[j - i]$
注意初始化$f[0]=1$,选出$0$的方案，什么都不选就可以了，也算一种方案。
```cpp
sum = s / 2;//s是1 ~ n的和
f[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = sum; j >= i; j--)
{
f[j] += f[j - i];
}
}
cout << f[sum] / 2;//除以2，避免顺序问题重复计算
```
[背包计数](https://www.luogu.com.cn/problem/P1832)
筛法预处理质数，然后就可以像上一个题一样使用背包问题求解方案数。
### 完全背包
每个物品有无限种选择(其实无法选择无限个，主要容量有限)，因此对于上面的状态转移有一定区别。
每一个$f_{i,j}$对于选与不选来考虑，应该从选$0,1,2,3\dots$个第$i$个物品来转移，所以求取$f_{i,j}$应该是选$0,1,2,3\dots$个第$i$个物品的状态来取$\max$
首先选$0$个，就是不选，所以就是$f_{i-1,j}$
选$1$个，就是$f_{i-1,j-v_i}+w_i$
选$2$个，就是$f_{i-1,j-2 * v_i}+w_i * 2$
$\dots$
选$s$个，就是$f_{i-1,j-s * v_i}+w_i * s$
朴素转移，自然是枚举第$i$个物品选择了多少个，这样一来加大了转移的时间复杂度。
也就是$f_{i,j}=max(f_{i-1,j},f_{i-1,j-v_i}+w_i,f_{i-1,j-2 * v_i}+w_i * 2,\dots,f_{i-1,j-s * v_i}+w_i * s)$
考虑优化：
主要挖掘不同状态之间的关系
我们来研究一下$f_{i,j-v_i}$这个状态。还是跟上面一样的转移思路，枚举第$i$个选择$0,1,2,\dots$个。
$f_{i,j-v}=\max(f_{i-1,j-v},f_{i-1,j-2v}+w,f_{i-1,j-3v}+2w,\dots,f_{i-1,j-s*v}+(s-1)w)$
注意：这里的$s$和上面的$s$都是一个数字(其实就是$\lfloor \frac{V}{v_i} \rfloor$)，因为我们都是针对第$i$个物品无限选择下去直到超过容量限制。
跟上面的相比，发现是一模一样的，就是在$f_{i,j-v}$的基础上多了一个$w$
因此完全背包的转移方程为$f_{i,j}=\max(f_{i-1,j},f_{i,j-v_i}+w_i)$
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, W, dp[105][1005], v[105], w[105];
int main()
{
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= W; j++)
{
if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
else dp[i][j] = dp[i - 1][j];
}
}
cout << dp[n][W];
return 0;
}
```
由于转移只和$i-1$这一维有关，因此可以采用滚动数组优化。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, W, dp[2][1005], v[105], w[105];
int main()
{
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= W; j++)
{
if (j >= w[i]) dp[i & 1][j] = max(dp[i - 1 & 1][j], dp[i & 1][j - w[i]] + v[i]);
else dp[i & 1][j] = dp[i - 1 & 1][j];
}
}
cout << dp[n & 1][W];
return 0;
}
```
甚至可以直接优化掉第一维，循环必须正着枚举，这里要注意，任何背包问题在优化掉第一维只有完全背包正着写，其余都是倒着。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, W, dp[1005], v[105], w[105];
int main()
{
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = w[i]; j <= W; j++)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[W];
return 0;
}
```
[模板题](https://www.luogu.com.cn/problem/P1616)
[变形题](https://www.luogu.com.cn/problem/P2918)
### 多重背包
多重背包的变化在于，每个物品可以选择$0,1,2,\dots,s_i$个，这里的$s_i$不一定和$\lfloor \frac{V}{v_i} \rfloor$相同，因此不能按照完全背包的方式实现$O(1)$的转移。
转移方程为：$f_{i,j}=max(f_{i-1,j},f_{i-1,j-v_i}+w_i,f_{i-1,j-2 * v_i}+w_i * 2,\dots,f_{i-1,j-s_i * v_i}+w_i * s_i)$
所以在转移的时候，我们必须在写一个循环来枚举选择了多少个。
```cpp
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++){
for (int j = t; j >= 0; j--){
for (int k = 1; k <= s[i]; k++){
if (j >= v[i] * k) dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);
}
}
}
cout << dp[t];
```
若$s_i$较大，转移会比较费时，这里引入这样一个问题来解决它的优化。
若要凑出$0,1,2,3,\dots,100$这些数字，我们其实就用$0,1,2,4,8,16\dots$他们互相组合即可。
因此这里的做法就是对每一个$s_i$进行二进制拆分，一直拆$2$的次幂，最后剩一点不够了，就单独添加剩余的就行。
举几个例子
* `6=1+2+3`
* `8=1+2+4+1`
* `18=1+2+4+8+3`
* `31=1+2+4+8+16`
优化方式称为：二进制优化
```cpp
cin >> n >> W;
for (int i = 1; i <= n; i++)
{
cin >> v1 >> w1 >> s1;
// 价值， 体积， 可以选择的个数
int c = 1;//初始化为1
while (s1 - c > 0)
{
s1 -= c;
v[++cnt] = c * v1;
w[cnt] = c * w1;
c *= 2;//每次乘以2
}
v[++cnt] = s1 * v1;//可能s1有剩余，或者也可以判断一下s1是否大于0
w[cnt] = s1 * w1;
}
for (int i = 1; i <= cnt; i++)//现在相当于有cnt个物品做01背包了
{
for (int j = W; j >= w[i]; j--)
{
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
```
具体时间复杂度还要看$s_i$的大小，$while$循环的复杂度自然是$log{s_i}$
[宝物筛选](https://www.luogu.com.cn/problem/P1776)
单调队列优化多重背包，本方法难度较大，且普及组不适用，暂不罗列。
这里主要是类比完全背包的写法，写清楚一大堆转移以后，发现了一个滑动窗口，进而对所有$j\equiv r \mod v $的$j$进行滑动窗口求最值，最终可以让时间复杂度降到$O(nV)$
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 5;
int n, V, f[2005][20005], q[20005], v[20005], w[20005], s[20005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++)
{
for (int r = 0; r < v[i]; r++)
{
int h = 0, t = -1;
for (int j = r; j <= V; j += v[i])
{
while (h <= t && j - q[h] > s[i] * v[i]) h++;
while (h <= t && f[i - 1][j] >= f[i - 1][q[t]] + (j - q[t]) / v[i] * w[i]) t--;
q[++t] = j;
f[i][j] = f[i - 1][q[h]] + (j - q[h]) / v[i] * w[i];
}
}
}
cout << f[n][V];
return 0;
}
```
### 混合背包
分别处理即可
```cpp
for (循环物品种类) {
if (是 0 - 1 背包)
套用 0 - 1 背包代码;
else if (是完全背包)
套用完全背包代码;
else if (是多重背包)
套用多重背包代码;
}
```
[樱花](https://www.luogu.com.cn/problem/P1833)
$80$分代码
```cpp
cin >> s1 >> c >> e1 >> s2 >> c >> e2 >> n;
T = s2 * 60 + e2 - s1 * 60 - e1;//计算一下总时间，也就是背包容量
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i] >> p[i];
for (int i = 1; i <= n; i++)
{
if (p[i] == 0)
{
for (int j = v[i]; j <= T; j++)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
else
{
for (int j = 1; j <= p[i]; j++)
{
for (int k = T; k >= v[i]; k--)
{
f[k] = max(f[k], f[k - v[i]] + w[i]);
}
}
}
}
```
$100$分代码，需要优化，可以将无限选设置一个较大的数字，然后二进制优化，最终转变为$01$背包求解。
### 分组背包
有若干组，每一组有若干个物品，每一组物品只能选择一个，求最大值价值。
状态设计：$f[i][j]$为前$i$组物品中选，且总体积不超过$j$的最大价值
状态转移：枚举在第$i$组选了哪一个物品即可,选或不选。
$f[i][j] = max(f[i- 1][j],f[i-1][j-v[i][k]]+w[i][k])$
```cpp
cin >> n >> t;//组和容量
for (int i = 1; i <= n; i++)
{
cin >> s[i];//第i组有s[i]个
for (int j = 1; j <= s[i]; j++)
{
cin >> v[i][j] >> w[i][j];
}
}
for (int i = 1; i <= n; i++)//枚举组
{
for (int j = t; j >= 0; j--)//枚举容量
{
for (int k = 1; k <= s[i]; k++)//枚举这一组选哪个
{
if (j >= v[i][k]) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
}
}
}
cout << dp[t];
```
[通天之分组背包](https://www.luogu.com.cn/problem/P1757)
难点在于输入的记录，记录到每一组的信息，可以参考以下做法。
```cpp
for (int i = 1; i <= n; i++)
{
cin >> a >> b >> c;
cnt[c]++;
v[c][cnt[c]] = a;
w[c][cnt[c]] = b;
}
```
[机器分配](https://www.luogu.com.cn/problem/P2066)
将每个公司看成组，题目给出了每一组选$1,2,\dots,m$个的价值，消耗就是$1,2,\dots,m$
求字典序最小，倒着枚举物品做背包。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 15, M = 20;
int n, m, a[N][M], dp[N][M];
pair<int, int> f[N];
int path[N][M];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = n; i >= 1; i--)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k <= j; k++)
{
if (dp[i + 1][j - k] + a[i][k] > dp[i][j])
{
path[i][j] = k;
dp[i][j] = dp[i + 1][j - k] + a[i][k];
}
}
}
}
cout << dp[1][m] << "\n";
int i = 1, j = m;
while (i <= n && j > 0)
{
if (path[i][j])
{
f[i] = {i, path[i][j]};
j -= path[i][j];
}
i++;
}
for (int i = 1; i <= n; i++) cout << i << " " << f[i].second << "\n";
return 0;
}
```
### 有依赖的背包
[金明的预算方案](https://www.luogu.com.cn/problem/P1064)
有依赖就如同这个题的描述，选择某些物品必须选择某个物品后才能选择它。
该问题本质其实也是分组背包问题，例如主件电脑有附件打印机，扫描仪。
我们可以建立一个电脑组，组里有$4$种组合。
分别为：电脑，电脑+打印机，电脑+扫描仪，电脑+打印机+扫描仪。
显然问题就转变成了分组背包了，从每一组里选择一种组合而已。
可以看出一个主件若有$2$个附件，一共$4$种组合，其实就是$2^x$($x$为附件物品个数)
难点：
存储物品
这里我们可以用结构体和$vector$实现主件和附件的存储。
定义`pair<int, int> mas[N]`,若一个物品是主件，则记录`mas[i] = {v, v * w}//v是花费的金钱，v * w是题目说的价值`
定义`vector<pari<int, int> > ser[N]`存储附件，若是附件，则`ser[q].push_back({v, v * w})`
最后枚举每个物品，该物品是主件，就枚举主件和附件的所有组合，无非就是一个二进制枚举或`dfs`都行。
```cpp
#include <bits/stdc++.h>
#define ll long long
#define v first
#define w second
using namespace std;
const int N = 32005, M = 60;
int n, m, dp[N];
pair<int, int> mas[M];
vector<pair<int, int>> ser[M];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int V, p, q;
cin >> V >> p >> q;
if (!q)
{
mas[i] = {V, V * p};
}
else
{
ser[q].push_back({V, V * p});
}
}
for (int i = 1; i <= m; i++)
{
if (mas[i].v)
{
for (int j = n; j >= 0; j--)
{
int sz = ser[i].size();//主件 i 的附件个数
for (int k = 0; k < (1 << sz); k++)
{
int V = mas[i].v, W = mas[i].w;//对于每个状态先初始化V和W为选择了主件时的情况
for (int num = 0; num < sz; num++)
{
if (k & (1 << num))
{
V += ser[i][num].v, W += ser[i][num].w;
}
}
if (j >= V) dp[j] = max(dp[j], dp[j - V] + W);
}
}
}
}
cout << dp[n];
return 0;
}
```
### 二维费用背包
该类型就是每个物品有两个限制，重量和体积，背包也是两个容量，题目要求一般是体积不能超过，重量也得不能超过。
类比$01$背包加一维状态即可。
$f_{i,j,k}$为前$i$个物品，重量不超过$j$，体积不超过$k$的最大价值。
转移$f[i][j][k] = max(f[i-1][j][k],f[i-1][j-w[i]][k-v[i]])+value[i]$
同样也是可以使用倒序枚举去掉第一维的，两个限制注意倒序枚举即可。
[榨取kkksc03](https://www.luogu.com.cn/problem/P1855)
[潜水](https://www.luogu.com.cn/problem/SP181)
本题也是二维费用$01$背包，但是题目实际意思时选若干物品，体积和重量至少是$j,k$的情况。
状态设计：$f[i][j][k]$为前$i$个物品，氧气含量至少是$j$，氮气含量至少是$k$的最小重量。
转移：考虑是否加入第$i$个物品，$f[i][j] = max(f[i - 1][j][k], f[i - 1][j - v1][k - v2] + w)$
但这里发现和朴素$01$背包并无区别，但是状态设计含义完全不同，变成至少是，所以变化点在于$j-v1,k-v2$是可以小于$0$的，我们也必须由小于$0$的状态转移，比如我只需要凑出体积至少是$3$，现在选了这个物品，体积直接到达了$5$，显然是合法的，但是$3-5<0$。
因此转移修改为：$f[i][j] = max(f[i - 1][j][k], f[i - 1][max(0, j - v1)][max(0, k - v2)] + w)$
```cpp
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= k; i++)
{
int a, b, c;
cin >> a >> b >> c;
for (int j = m; j >= 0; j--)
{
for (int k = n; k >= 0; k--)
{
dp[j][k] = min(dp[j][k], dp[max(j - a, 0)][max(0, k - b)] + c);
}
}
}
cout << dp[m][n];
```
### 三种状态总结
* 选出若干个物品，不超过体积$j$的情况，也就是体积最多是$j$
初始化：全部初始化为$0$，求解时保证$j\geq v$方可求解$f[i][j]$
* 选出若干个物品，体积恰好是$j$的情况
初始化：只有$f[0][0] = 0$,其余如果求最大值就初始化负无穷，求最小值就初始化正无穷。
* 选出若干个物品，体积至少是$j$的情况
初始化：只有$f[0][0] = 0$,其余如果求最大值就初始化负无穷，求最小值就初始化正无穷，转移的时候可以从$j\leq v$的$f[i][j - v]$转移，即$f[i][max(0, j - v)]$。
### 背包问题求方案
以$01$背包为例
$f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w)$
其实就是判断每个物品是否被选，对应的问题也有在图论最短路中输出最短路径是什么。
例如$f[n][m] = max(f[n - 1][m], f[n - 1][m - v] + w)$
假如求出选择了第$n$个物品，问题等价于是$f[n - 1][m] == f[n][m]$还是$f[n - 1][m - v] + w == f[n][m]$,或者比较二者大小也行。当然也有可能二者相等，那么第$n$个选和不选就无所谓了。
正常求方案，由于方案不唯一，大概记录一下选了哪些就行。
```cpp
for(int i = 1; i <= n; i++)
{
for (int j = m; j >= v[i]; j--)
{
if (dp[j - v[i]] + w[i] > dp[j])
{
path[i][j] = true;//选了第i个
dp[j] = dp[j - v[i]] + w[i];
}
}
}
int j = m, i = n;
while (i > 0 && j > 0)
{
if (path[i][j])
{
cout << i << " ";
j -= v[i];
}
i--;
}
```
[背包问题求具体方案](https://www.acwing.com/problem/content/12/)
本题解决字典序最小，可以采用贪心的思路。即我从第$1$个物品开始考虑。
对于第$1$个物品分为三种情况：
* 必须选第$1$个
* 不选第$1$个
* 可选可不选，为了字典序最小优先选$1$
然后顺次考虑后面的物品。为了方便起见，我们在循环的时候直接从大到小循环去做每个物品，这样最后记录的必然是优先选择前面的。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 5, M = 1e3 + 5;
int n, V, dp[N][N], v[N], w[N];
bool path[N][M];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = n; i >= 1; i--)//倒着做
{
for (int j = 0; j <= V; j++)
{
dp[i][j] = dp[i + 1][j];
if (j >= v[i])
{
if (dp[i + 1][j - v[i]] + w[i] >= dp[i][j])
{
dp[i][j] = dp[i + 1][j - v[i]] + w[i];
path[i][j] = 1;
}
}
}
}
int i = 1, j = V;
while (i <= n && j > 0)
{
if (path[i][j])
{
j -= v[i];
cout << i << " ";
}
i++;
}
return 0;
}
```