背包问题
背包问题是一类很大的问题，很多问题都能转化成背包问题。
01背包
01背包问题的特点是所有物品仅能用一次
状态转移方程
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);二维版本
定义二维数组f[i] [j]表示一个状态，i标志前i个物品（有序），在背包容量为j下的最优解。
用一个二重循环迭代整个过程，外层循环i，表示前i个物品，内层循环j，表示背包容量为j下，对第i个物品是否选择。因为在同一层i的循环下，随着j的增大，f[i] [j]是不可能变小的，所以最后f[n] [m]一定是我们的最优解。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][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 (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}为何可以变为一维？
(1) 计算f[i]时只用到了f[i - 1]
(2) 在f[i]中用到的状态严格小于j
为何内层循环从大到小判断
我们用到的是滚动数组，更新f[i] [j]是应该用到f[i - 1]层，但如果从小到大判断，我们用到的f[j - v[i]] 就应该是f[i] [j] 而不是f[i - 1] [j]。
优化输入
在计算f[i]时其实只用到了f[i - 1]，因此我们可以边输入边进行计算：
for (int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w);
}最终版本
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}超大01背包
一道思路比较清奇的题（可能是蒟蒻见识少）。
Atcoder Educational DP Contest E - Knapsack 2
题目大意：给定n个物品和一个容积为W的背包，每个物品都有一个价值v和一个质量w（与01背包要求相同），求能装下的最大价值。
该题不同的一点是数据范围，物品的质量高达了1e9，用普通的01背包，就算一维优化，也开不了这么大的数组。
该题的思路就是将价值和质量转换，令f[i]为价值为i下的最小体积（因为总价值只有1e5的范围，可以暴力枚举）。
AC代码（开longlong）：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
//#include <unordered_map>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <cctype>
#include <vector>
#include <string>
using namespace std;
#define IOS \
cin.tie(0), cout.tie(0); \
ios::sync_with_stdio(false);
#define int long long
#define endl '\n'
#define x first
#define y second
typedef pair<int, int> PII;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
const int mod = 100000007;
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m;
int q[maxn];
int f[maxn];
struct node
{
int x, y;
} t[maxn];
bool cmp(node a, node b)
{
return a.x < b.x;
}
void solve()
{
cin >> n >> m;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i ++ ){
int w, v;
cin >> v >> w;
for (int j = 100000; j >= w; j -- ) f[j] = min(f[j], f[j - w] + v);
}
int ans = 0;
for (int i = 1; i <= 100000; i ++ ){
if (f[i] <= m) ans = max(ans, i);
}
cout << ans << endl;
}
signed main()
{
IOS;
tt = 1;
//cin >> tt;
while (tt -- )
solve();
return 0;
}完全背包问题
完全背包问题的特点是每件物品有无限个
状态转移方程
f[i][j] = max(f[i][j], f[i][j - k * v[i]] + k * w[i]);朴素版本
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
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++)
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
cout<<f[n][m]<<endl;
}如何优化？
f[i][j] = max(f[i - 1][j] + f[i - 1][j - v] + w, f[i - 1][j - 2 * v] + 2 * w ...);
f[i][j - v] = max(f[i - 1][j - v], f[i - 1][j - 2 * v] + w, ...);因此
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);加上一个一维的优化，我们就可以将三重（伪）的循环变为一维
注意我们的状态转移方程，这次用到的都是f[i]一层，因此不需要反向循环，在同一个i中可以用更新过的数据继续更新下一个，这是和01背包的不同之处。
同时，我们也可以使用优化输入，边读入边计算。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for (int j = v; j <= m; j ++ ) f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}多重背包问题
多重背包特点是每件物品最多有Si个
其实只是完全背包问题加上一个判断条件，因此可以通过朴素版的完全背包问题来修改
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
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 - v[i] * k] + w[i] * k);
cout << f[n][m] << endl;
return 0;
}因为是三重循环，因此时间复杂度非常高，在N=100的数据范围就进行了1000000次运算，所以局限性非常大。
在完全背包中我们使用的优化在多重背包中不能使用，原因是max不支持加减操作，在完全背包中我们只是进行了简单的代换，而在此处多了一项。
二进制优化
倍增的思想：
假设现在的si是1023，那么我们可以把这个1023分成10份，分别为1,2,4,8…,512，这十组里任取一个数，全部相加就可以得到0~1023中的任何一个数。所以我们可以把这几组当作01背包处理，每次选或不选。
凑出Si
设Si，接着从1到2^k，2^k是小于Si的最大的2的倍数，设定一个c用来凑齐Si，即12^k可以表示出02^k+1的所有数，加上c后可以表示出cSi的所有数，将两集合合并，即可得到0Si的所有数。
#include <bits/stdc++.h>
using namespace std;
const int N = 12000, M = 2020;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
cin >> n >> m;
int cnt = 0; // 表示下标
for (int i = 1; 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 *= 2;
}
if (s > 0){ // 表示有c的存在
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;
return 0;
}单调队列优化
能比二进制优化处理更多的数据，也比较好写（
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m;
int f[N], g[N], q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j ++ )
{
int hh = 0, tt = -1;
for (int k = j; k <= m; k += v)
{
if (hh <= tt && q[hh] < k - s * v) hh ++ ;
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
q[ ++ tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}分组背包问题
分组背包问题的特点是物品有N组，每组里只能选一个物品。
和完全背包问题类似。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[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] << endl;
return 0;
}二维费用的背包问题
其实二维费用的背包问题和一维费用十分相似，只需要将状态表示多一维即可。
二维费用的01背包问题模板：
#include <iostream>
using namespace std;
const int maxn = 1010;
int n, V, M;
int f[maxn][maxn]; // 表示不超过i的第一费用，j的第二费用的最大价值。
int main()
{
cin >> n >> V >> M;
for (int i = 1; i <= n; i ++ ){
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; j -- ){
for (int k = M; k >= m; k -- ){
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
}
}
cout << f[V][M] << endl;
}可见，二维费用的背包问题和一维费用背包问题的最大区别是状态表示多一维，且多加一个循环用于表示另外一重费用。
