背包
动态规划中的背包问题
01背包
有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。
分析： 考虑前i个物品，总体积为j时分为两种情况： 第i个物品没取，问题变成了考虑了前 i−1个物品，总体积为j时的情况； 第i个物品取了，问题变成了考虑了前i −1个物品，总体积为j-v[i]时的情况；
状态：f[i][j]表示考虑了前i个物品，总体积为j时的最大收益。 转移：分别对应第i个物品没取f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])和取了两种情况。
错误写法
根据状态转移方程写出了这样的代码：
int n, m;
int f[1010][1010];
int v[1010], w[1010];
signed 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[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}在这个写法中，当j<=v[i]时，数组没有被更新，因此发生错误
正确写法
int n, m;
int f[1010][1010];
int v[1010], w[1010];
signed 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++) {
if(j<v[i]) f[i][j] = f[i - 1][j];
else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}滚动数组
但是当数据过大时，使用二维数组占用的空间太大，由于在计算i行时只用到了i-1行，所以可以用一个g数组存i-1行的数据，循环滚动f和g
int f[1010], g[1010];
int v[1010], w[1010];
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++) {
if (j >= v[i]) g[j] = max(f[j], f[j - v[i]] + w[i]);
else g[j] = f[j];
}
memcpy(f, g, sizeof(g));
}
cout << f[m] << endl;
return 0;
}一维做法
状态：用f[i]表示总体积为i时的最大收益。 转移：f[j] = max(f[j], f[j - v[i]] + w[i])表示取前i个物品总体积为j时的最大情况
注意在枚举体积时，要从大向小枚举，若小到大枚举，则在枚举过程中可能会多次放入同一物品
int f[1010];
int v[1010], w[1010];
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 = v[i]; j <= m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}完全背包
有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，每种物品能用无限多次，问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。
完全背包的区别就是每个物品可以拿无数次
分析： 考虑前i个物品，总体积为j时分为两种情况： 第i个物品没取，问题变成了考虑了前 i−1个物品，总体积为j时的情况； 第i个物品取了，问题变成了考虑了前i 个物品，总体积为j-v[i]时的情况；
状态：用f[i][j]表示考虑了前i个物品，总体积为j时的最大收益。 转移：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])分别对应第i个物品没取和取了两种情况。
普通做法：
int n, m;
int f[1010][1010];
int v[1010], w[1010];
signed 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++) {
if (j < v[i]) f[i][j] = f[i - 1][j];
else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}一维做法： 因为完全背包就是在01背包的基础上每个物品可以拿无数次，因此在枚举体积时正向枚举，即可在体积允许的情况下，将多个同一物品放入背包。
int f[1010];
int v[1010], w[1010];
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 = v[i]; j <=m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}延伸
如果要让背包里的物品体积正好是m，应该怎么做呢？
只需要把f数组初始化为负无限大，然后让f[0]=0，这样只有在体积刚好凑成的时候f才能数组才能被更新。
int f[1010];
int v[1010], w[1010];
int main() {
int n, m;
cin >> n >> m;
memset(f, 128, sizeof(f));
f[0] = 0;
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;
}多重背包
有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，可以用l[i]次。问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。
分析：
第i种物品可以使用l[i] 次，我们可以把它拆成l[i]个物品，每个物品只能用一次； 然后就是个01背包问题啦!
int f[1010];
int v[1010], w[1010], l[1010];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> l[i];
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= l[i]; k++) {
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;
}但是当数据过大时，这种做法会超时，可以采用二进制分组优化
二进制分组优化
从1,2,…,2m中选一些数字相加，可以得出任意[0,2m+1)内的值，每个数字只能用一次；
利用这条结论，我们可以用二进制表示体积m，例如：
5=1+4 6=2+4 7=1+2+4 8=1+1+2+4
因此对于第i种物品，可以使用l[i]次，那么可以把它拆成O(log n)个物品，每个物品只能用一次；
int f[2010];
int v[2010], w[2010], l[2010];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> l[i];
}
for (int i = 1; i <= n; i++) {
int res = l[i];
for (int k = 1; k <= res; res -= k, k *= 2) {
for (int j = m; j >= v[i] * k; j--) {
f[j] = max(f[j], f[j - v[i]*k] + k*w[i]);
}
}
for (int j = m; j >= v[i] * res; j--)
f[j] = max(f[j], f[j - res * v[i]] + res * w[i]);
}
cout << f[m] << endl;
return 0;
}分组背包
有n种物品要放到一个袋子里，袋子的总容量为m。第i个物品属于第a[i]组，每组物品我们只能从中选择一个。第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益。问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。
分析： 把考虑了前i组物品以后，总体积为0，1，...，m时的最大收益都记下来； 考虑了前i组物品，总体积为j时分为两种情况： 第i组物品一个没取，问题变成了考虑了前 i−1组物品，总体积为j时的情况； 第i组物品取了，我们枚举取了其中的物品k，问题变成了考虑了前 i−1组物品，总体积为 j−v[k]时的情况； 状态：用f[i][j]表示考虑了前i组物品，总体积为j时的最大收益。 转移：f[i][j]= max (f[i-1][j], f[i-1][j-v[k]]+w[k])),其中c[i]表示第i组中物品的编号集合。
int n, m;
int f[1010][1010];
int v[1010], w[1010], a[1010];
vector<int>c[1010];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> v[i] >> w[i];
c[a[i]].push_back(i);
}
for (int i = 1; i <= 1000; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
for (auto k : c[i]) {
if (v[k] <= j)
f[i][j] = max(f[i][j], f[i - 1][j - v[k]] + w[k]);
}
}
}
cout << f[1010][m] << endl;
return 0;
}一维做法
int n, m;
int f[1010];
int v[1010], w[1010], a[1010];
vector<int>c[1010];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> v[i] >> w[i];
c[a[i]].push_back(i);
}
for (int i = 1; i <= 1000; i++) {
for (int j = m; j; j--) {
for (auto k : c[i]) {
if (v[k] <= j)
f[j] = max(f[j], f[j - v[k]] + w[k]);
}
}
}
cout << f[m] << endl;
return 0;
}二维背包
有n种物品要放到一个袋子里，袋子的总容量为m，我们一共有k点体力值。第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，并且消耗我们t[i]点体力值，每种物品只能取一次。问如何选择物品，使得在物品的总体积不超过m并且花费总体力不超过k的情况下，获得最大的收益？请求出最大收益。
分析： 把考虑了前i个物品以后，总体积为0，1，...，m，总体力为0，1，...k时的最大收益都记下来； 考虑了前i个物品，总体积为j，总体力为x时分为两种情况： 第i个物品没取，问题变成了考虑了前 i−1个物品，总体积为j，总体力为x时的情况； 第i个物品取了，问题变成了考虑了前 i−1个物品，总体积为 j−v[i],总体力为x-t[i]时的情况； 状态：用f[i][j][x]表示考虑了前i个物品，总体积为j，总体力为x时的最大收益。 转移：f[i][j][x]=max(f[i−1][j][x],f[i−1][j−ν[i]][x−t[i]]+w[i])
这里就不贴普通做法的三维数组做法了，直接贴二维
int n, m, k;
int v[1001], w[1001], t[1001];
int f[1001][1001];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> t[i];
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
for (int x=k; x >= t[i]; x--) {
f[j][x] = max(f[j][x], f[j - v[i]][x - t[i]] + w[i]);
}
}
}
cout << f[m][k] << endl;
return 0;
}单调队列
有n个生物，第i个生物会在第i到第a[i]天出现，它的攻击力为b[i]。其中对于所有i(1≤i<n)，满足a[i]≤a[i]+1。请输出每天出现的生物的攻击力的最大值。
分析： 假设现在考虑到了第i天，对于第 j(j<i)个生物，如果 b[j]<b[i],那么之后第j个生物都不用考虑了(在它存在期间，永远被第i个生物压制) ； 用一个队列，按编号从小到大的顺序，存放到目前为止，哪些生物是需要被考虑的(有可能在未来的某一天成为攻击力最高的生物) ；
int n, a[100010], b[100010], c[100010][2];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &a[i], &b[i]);
}
int k = 0, l = 1;
for (int i = 1; i <= n; i++) {
for (; k >= l && b[i] >= c[k][0]; --k);//删掉队尾攻击力小的
c[++k][0] = b[i]; c[k][1] = a[i];
printf("%d\n", c[l][0]);
for (; k >= l && c[l][1] == i; ++l);//删掉队头已经超过时限的元素
}
return 0;
}//选择数字P
int head = 1, tail = 1;
for (int i = 1; i <= n; i++) {
dp[i] = q[head] + a[i];
while (head <= tail && q[tail] >= dp[i]) tail--;
q[++tail] = dp[i], p[tail] = i;
while (head <= tail && p[head] < i - k) head++;
}多重背包
有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，可以用l[i]次。问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。
分析： 把考虑了前i种物品以后，总体积为0，1，…，m时的最大收益都记下来； 考虑了前i种物品，总体积为j时分为两种情况：
第i种物品没取，问题变成了考虑了前 i−1种物品，总体积为j时的情况；
第i种物品取了，枚举它取了k次，问题变成了考虑前 i−1 种物品，总体积为 j−v[i]×k时的情况；
状态：用f[i][j]表示考虑了前i种物品，总体积为j时的最大收益。
转移： f[i][j]=max(f[i−1][j],max f[i−1][j−v[i]×k]+w[i]×k)
把j按照 mod v[i]分类，只有同一类的状态间可以进行转移； 例如：当 v[i]=4时，其中一类为1，5，9，13，... 在某一类中下标为k的位置，可以转移到下标在 [k+1,k+l[i]]中的位置； 每个位置取最大值， 下标k，x之间转移的时候，(x−k)*w[i]怎么处理? 要求max(f[k]+(x−k)*w[i])，f[k]表示某一类中下标为k时的最值；因为x*w[i]对于每个位置是定值； 所以把 f[k]−k*w[i]放进单调队列就行啦！
int n, m, v, w, l,t, f[10001], c[10001][2];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> t;
for (int j = 0; j < v; j++) {
int k = 0, l = 1;//k是尾指针，l是头指针
for (int pos = j, x = 1; pos <= m; pos += v, ++x) {
int e = f[pos] - x * w, r = x + t;
for (; k >= l && c[k][0] <= e; --k);
c[++k][0] = e; c[k][1] = r;
f[pos] = c[l][0] + x * w;
for (; k >= l && c[l][1] == x; ++l);
}
}
}
cout << f[m] << endl;
return 0;
}
Last updated