常见的背包类型
- 01背包:每个物品要么选,要么不选(只能选0或1个)
- 完全背包:每个物品无限制选择数量
- 多重背包:每个物品最多有s个
- 分组背包:每组物品有若干个,同一组内的物品最多只能选一个
动态规划的思路
DP
- 状态表示:决定用几维来表示(怎么表示)f(i, j)
- - 集合
- - - 所有选法
- - - 条件:1-前i个物品中选;2-总体积 ≤ j
- - 属性:max、min、数量
- 状态计算(怎么计算)
DP优化:对动态规划的代码或者方程做等价变形
思考过程:不要上来就用优化方法,要尝试用简单的朴素方法解决问题,再思考有没有优化改进的空间,使得问题的思考曲线不至于很陡峭。
DP分析
状态表示
状态计算
01背包
每件物品选0个还是1个
分析
朴素代码(二维数组)
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d %d", &v[i], &w[i]);
// f[i][j] 从前i个物品中挑选,使得总体积≤j
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][j], f[i-1][j-v[i]] + w[i]);
}
printf("%d", f[n][m]);
return 0;
}
优化代码(一维数组)
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d %d", &v[i], &w[i]);
// 因为计算第i层只用了第i-1层,且计算j,只用了j-v[i](<=j)
// 为了在计算完成之前,不覆盖旧数据,从大到小计算
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]);
printf("%d", f[m]);
return 0;
}
完全背包
每个物品的数量是无限个,0、1、2、、、、
分析
朴素写法
#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() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d %d", &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]] + w[i] * k);
printf("%d", f[n][m]);
return 0;
}
测试数据被加强了,如果不改进,就过不了
优化分析
优化代码
#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() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d %d", &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]);
}
printf("%d", f[n][m]);
return 0;
}
再优化:二维转化为一维
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d %d", &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]);
printf("%d", f[m]);
return 0;
}
因为计算第i层,使用的是第i层,且 j–v[i] ≤ j,所以要从前往后计算
如果从后往前计算,第i层前面的数据还没更新,也就无法计算出第i层后面的数据
与01背包优化的区别是,计算第i层要用第i-1层的数据,且使用的是前面的旧数据,所以必须在计算出前面数据之前,把前面的数据使用掉,所以才会从后往前计算。
而这里,使用的是第i层的新数据,只有从前往后计算,才能保证前面的新数据被后面的计算利用。
多重背包 I、II
每个物品有s[i]个
分析
朴素写法
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d %d %d", &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] + k * w[i]);
printf("%d", f[n][m]);
return 0;
}
二进制优化方法
第i种物品有s[i]个,将s[i]个物品拆成多种以2的幂次为单位的物品
假如第i种物品有1000个,可以拆成1、2、4、8、16、32、64、128、256、488
将拆分出来每种数量的物品看成是一个物品,采用01背包的方法,可以表示0~1000范围内的物品
1个第i物品一组,2个第i个物品一组,4,8,16…..
原来复杂度是NVS,可以降到 NVlogS
分析
数据范围估计,应该开多大的数组,N = 1000种物品 * log(每种物品最多si件)
S -> logS就是一种多件拆成多种1件 的过程,N = 1000 * 11
const int N = 11010, M = 2010; // 改成11010也能通过,说明上述想法是对的
二进制优化后代码
#include <iostream>
using namespace std;
const int N = 25000, M = 2010; // N 优化后的物品种数 M 总体积
int n, m;
int v[N], w[N];
int f[N];
int main() {
scanf("%d %d", &n, &m);
int cnt = 0; // 优化后的物品真实种数,将所有第i件物品拆分后的种数
for (int i = 1; i <= n; i ++) {
int a, b, s;
scanf("%d %d %d", &a, &b, &s);
int k = 1; // 每个第i件物品按二进制拆分出来的物品数量
while(k <= s) { // 将s件物品拆成 1, 2, 4, , ,2^k , , , s
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
// 不足2的幂次数量的第i件物品,剩余部分
if (s > 0) {
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; // 将多重背包问题转化为拆分后物品的01背包问题
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]);
printf("%d", f[m]);
return 0;
}
分组背包
朴素写法(小数据量正确,大数据量错误,不知道错在什么地方?)
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N][N];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%d", &s[i]);
for (int j = 1; j <= s[i]; j ++) {
scanf("%d %d", &v[i][j], &w[i][j]);
}
}
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
for (int k = 1; k <= s[i]; k ++) {
f[i][j] = f[i-1][j];
if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]); // 第i组第k个物品
}
printf("%d", f[n][m]);
return 0;
}
优化写法
按照上面朴素写法优化后,大数据量计算没有出错
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%d", &s[i]);
for (int j = 1; j <= s[i]; j ++) {
scanf("%d %d", &v[i][j], &w[i][j]);
}
}
for (int i = 1; i <= n; i ++)
// 计算第i层需要第i-1层数据,且j-v[i][k] ≤ j,要使用旧数据,所以要从后往前算
for (int j = m; j >= 0; j --)
for (int k = 1; k <= s[i]; k ++) {
// 第i组第k个物品
if (j >= v[i][k]) f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
}
printf("%d", f[m]);
return 0;
}