导读 ^ _ ^
背包问题是动态规划的入门经典问题。
本文将讲解四种常见的背包问题及其优化方法。
背包分类
每 件/种 物品体积Vi
不超过背包容量的总价值最大化W（不一定装满）
01背包与动态规划思路
代码实现（二维朴素法）
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];//默认初始为0
int dp[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++) {
dp[i][j] = dp[i-1][j];
if(j>=v[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);
}
cout<<dp[n][m]<<endl;
return 0;
}
代码实现（滚动数组，状态压缩）
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int dp[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 = m; j >= v[i]; j--) {
//这里空集部分判断直接挪到循环里面
//不用推导，直接继承上一层
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
cout<<dp[m]<<endl;
return 0;
}
完全背包与数列推导优化
最朴素的思路起点
代码实现（显然会超时，1000三次方过亿次了，C++的 1s 大体运行一亿次）
#include<iostream>
#include<algorithm>
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++)
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;
return 0;
}
DP常见的数列推导优化
推导递推公式，常减去一项来观察规律实现降维。
#include<iostream>
#include<algorithm>
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][j-v[i]]+w[i]);
}
cout << f[n][m]<<endl;
return 0;
}
状态压缩
区分 01背包(全上层) 和 完全背包(本层+上层) 的遍历顺序。
#include<iostream>
#include<algorithm>
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++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = v[i]; j<= m; j++) {
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
cout << f[m]<<endl;
return 0;
}
多重背包与二进制枚举优化
最朴素的思路起点（如果数据过大和完全背包一样超时）
#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*v[i] <= j && k <= s[i]; k++) {
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
cout << f[n][m]<<endl;
return 0;
}
二进制枚举优化
比如要枚举0->1023中所有的数能不能凑成其中任意一个数
我们平常的枚举方法就是：0,1,2,3,4,5,…,1023。这样枚举1024次
使用二进制枚举优化，就可以只需枚举10次就可以枚举出任意一个数。
将0~1023这1024个数分为10个组，
每组分别是：1 2 4 8 16 32 64 128 256 512 这10个数字(2^0 2^1 2^2 … 2^9)。
在枚举的时候只枚举这10个数字，选或不选。就可以枚举出0~1023中的任意一个数字
二进制枚举优化代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25000;
int n,m;
int v[N],w[N];
int f[N];
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) {
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;
}
分组背包与状态压缩总结
和01背包特别像，不过多一个组内选择
状态压缩以及遍历顺序的总结
只要是上一层推导的，则从后往前
如果是同层推导的，则从前往后
只要是由上层某个方向定向推来的，就可以进行状态压缩
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int v[N][N],w[N][N],s[N];
int f[N];
int n,m;
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> 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 = m; j >= 0; j--)
for(int k = 1; k <= s[i]; k++)
if(j >= v[i][k]) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]);
cout << f[m] << endl;
return 0;
}