Algorithm2.1 背包dp
[TOC]
背包dp
背包问题总结
-
01背包：每种物品仅一个
- 最大化所有物品的总价值：基础01背包
- 组成当前容量的物品组合数：装配组合问题、路径问题
-
完全背包：每种物品有无限个
-
多重背包：每种物品有具体个数
-
分组背包：每种物品仅一个，且不同物品有自己所属的组别
-
多维代价背包：每种物品不仅占用空间，而且占用金钱
-
多维目的背包：每种物品不仅具有价值1，而且具有价值2
01背包
固定容量 最大价值
题目一
https://www.luogu.com.cn/problem/P1048
题目大意：给定背包容量，将价值总和最大化。
思路：dp[j]表示容量为j的最大价值。将当前dp[0]~dp[j]这j个容量/状态/问题，通过第i个商品转移到dp[-w[i]]~dp[j-w[i]]，n个商品就有n次刷新j个状态的过程。
#include <iostream>
using namespace std;
#define maxn 1005
int t, m, val[maxn], c[maxn], dp[maxn]; // dp[j]代表在容量为j的最大价值
int main() {
scanf("%d%d", &t, &m);
for (int i = 0; i < m; ++i) scanf("%d%d", &c[i], &val[i]);
for (int i = 0; i < m; ++i)
for (int j = t; j >= c[i] ; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
printf("%d\n", dp[t]);
return 0;
}
题目二
https://www.luogu.com.cn/problem/P1802
题目大意：给定容量和经验，其中付出固定容量得到胜利的经验，不付出（或者付出部分）容量都得到失败的经验。使最终经验最大化。
思路：首先优化题目，失败的情况下，无论如何都不付出任何容量。转化为最基础的01背包。用dp[j]表示容量为j的最大经验。将当前dp[0]~dp[j]这j个容量/状态/问题，通过第i个商品转移到dp[-w[i]]~dp[j-w[i]]。单独拿出一个状态dp[j]，在转换的时候用第i个商品，要么用容量去买，得到胜利的经验；要么直接不用，容量没损耗，经验加上失败的经验。
#include <iostream>
using namespace std;
#define maxn 1005
int n, x, l[maxn], w[maxn], c[maxn], dp[maxn]; // dp[j]表示在药水瓶数为j时所获得的最大经验
int main() {
scanf("%d%d",&n, &x);
for (int i = 0; i < n; ++i) scanf("%d%d%d",&l[i], &w[i], &c[i]);
for (int i = 0; i < n; ++i)
for (int j = x; j >= c[i]; --j)
dp[j] = max(dp[j-c[i]]+w[i], dp[j]+l[i]);
printf("%d\n", dp[x]*5);
return 0;
}
01背包内圈遍历方向问题
关键：dp[0]和dp[m]的赋值是否为1的问题。
理解：从大容量往小容量遍历，因为最后一位dp[m]没有被赋值为1，那么就没办法往前累加，每隔当前第i个商品的容量就要累加一次。反之从小往大遍历，第一位dp[0]是1，那么就会像滚雪球往后累计，每攒够第i个商品的容量，就要累加上一次。
装配组合//路径问题
题目一
https://www.luogu.com.cn/problem/P1164
题目大意：给定若干数，数值相同的数在组合中视作不同。问最大组合数（仅限加法的组合）。
思路：dp[j]表示组合成j时候的组合数。用第i个数来更改容量/状态为dp[0]~dp[j]的这些状态，通过dp[-w[i]]~dp[j-w[i]]进行转移。也就是这些状态之前的组合结果。将n个数，每次更改完的dp[j]都累加功效。
#include <iostream>
using namespace std;
#define maxn 102
#define maxm 10010
int n, m, a[maxn], dp[maxm]; // dp[i]表示容量为i的到达种类
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
// init
dp[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = m; j >= a[i]; --j)
dp[j] += dp[j-a[i]];
printf("%d\n", dp[m]);
return 0;
}
题目二
题目大意：和题目一区别在于，组合不仅可以加进去，也可以通过减法一块运算进去。
思路：将题目进行转换，就得到了纯加法进行组合的结果。
能否填充 // dp属性挑选与选取
https://www.luogu.com.cn/problem/P1510
题目大意：
1、如果dp属性选择到最大总容积上，dp[i]表示在容积为i时所需要的最小代价，再去比较代价 => 容积太大，不合适
2、如果dp属性选择到最大总代价上，dp[i]表示在代价为i时所呈现的最大容积，再去比较容积 => 合适
#include <iostream>
using namespace std;
#define maxn 10005
int vtotal, n, ctotal, val[maxn], c[maxn], dp[maxn]; // dp[i]表示在总代价为i时所获得的最大体积
// 初始化：
// 状态转移方程：dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
int main() {
scanf("%d%d%d", &vtotal, &n, &ctotal);
for (int i = 0; i < n; ++i) scanf("%d%d", &val[i], &c[i]);
for (int i = 0; i < n; ++i)
for (int j = ctotal; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
if (dp[ctotal] < vtotal) printf("Impossible\n");
else{
for (int i = 0; i < ctotal; ++i)
if (dp[ctotal-i] >= vtotal) continue;
else {printf("%d\n", i-1);break;}
}
return 0;
}
最小剩余容量 // 最大填充
https://www.luogu.com.cn/problem/P1049
题目大意：
#include <iostream>
using namespace std;
#define maxn 32
int ct, n, c[maxn], dp[maxn]; // dp[j]表示容量为j时所能凑出的最大容量。最后输出dp[j]即可
// 初始化：
// 状态转移方程：dp[j] = max(dp[j], dp[j-c[i]]+c[i]); // 根据能不能放进去，而获得的最大体积
int main() {
scanf("%d%d", &ct, &n);
for (int i = 0; i < n; ++i) scanf("%d", &c[i]);
for (int i = 0; i < n; ++i)
for (int j = ct; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+c[i]);
printf("%d\n", ct-dp[ct]);
return 0;
}
多重背包
模版
1、内核还是可以看成是乘倍数的01背包，所以中间遍历容量的时候要反向遍历，也就是从max_m往c[i]去刷新dp值
for (int i = 1; i <= n; ++i)
for (int j = w; j >= c[i]; --j)
for (int k = 1; k <= num[i] && k*c[i]<=j; ++k)
dp[j] = max(dp[j], dp[j-k*c[i]]+k*val[i]);
二进制优化
https://www.luogu.com.cn/problem/P1776
思路：通过二进制来将k这个可能的值用二进制给分解开，数据的两增加到了原来的logn倍，从原来的n^3的遍历缩减成了n^2的遍历加上logn的数据规模扩大。所以最后总的时间复杂度为n^2*logn
【二进制优化的思路很像快速幂，通过任何整数都可以通过2^0，2^1……的时候选取来拟合出来，2的多少次方，相乘也就是上面的指数2的0，2的1这样往后相加，所以也就优化成了最后的logn的复杂度凑出】
1、将原来的多重背包val，c，num拍平，成为一个二维的val，c。
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
for (int j = 1; j <= tc; j<<=1) {
c[++idx] = tb*j; val[idx] = ta*j;
tc-=j;
}
if (tc) {c[++idx] = tb*tc;val[idx] = ta*tc;}
}
2、将多重背包拍成了01背包之后，直接进行01背包的模版
for (int i = 1; i <= idx; ++i)
for (int j = m; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
完整AC代码
#include <iostream>
using namespace std;
#define maxn 1000100
int n, m ,ta, tb ,tc, c[maxn], val[maxn], idx = 0, dp[maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
for (int j = 1; j <= tc; j<<=1) {
c[++idx] = tb*j; val[idx] = ta*j;
tc-=j;
}
if (tc) {c[++idx] = tb*tc;val[idx] = ta*tc;}
}
for (int i = 1; i <= idx; ++i)
for (int j = m; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
printf("%d\n", dp[m]);
return 0;
}
单调队列优化
？？？ waiting
01背包 & 完全背包 & 多重背包混合
https://www.luogu.com.cn/problem/P1833
1、思路1:在遍历的时候，遍历到哪种种类背包就进行哪种遍历 => 完全背包直接完全遍历，01背包和多重背包直接用多重背包去解。（误
for (int i = 1; i <= n; ++i)
if (!c[i])
for (int j = c[i]; j <= m; ++j) dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
else
for (int j = m; j >= c[i]; --j)
for (int k = 1; k <= num[i] && j >= k*c[i]; ++k)
dp[j] = max(dp[j], dp[j-k*c[i]]+k*val[i]);
2、思路2:直接利用二进制优化，把完全背包和多重背包拍成01背包，原理就是通过完全背包看成一个无穷大的，例如99999等。
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
if (!tc) tc = 9999999;
for (int j = 1; j <= tc; j<<=1) {
c[++idx] = j*ta; val[idx] = j*tb;
tc -= j;
}
if (tc) {c[++idx] = tc*ta; val[idx] = tc*tb;}
}
for (int i = 1; i <= idx; ++i)
for (int j = m; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
完整AC代码：
#include <iostream>
using namespace std;
#define maxn 1000100
int bgh, bgm, edh, edm, m, n, ta, tb, tc, val[maxn], c[maxn], idx, dp[maxn];
int main() {
scanf("%d:%d %d:%d", &bgh, &bgm, &edh, &edm);
if (bgm > edm) {edm += 60; edh--;}
m = (edh-bgh)*60+(edm-bgm);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &ta, &tb, &tc);
if (!tc) tc = 9999999;
for (int j = 1; j <= tc; j<<=1) {
c[++idx] = j*ta; val[idx] = j*tb;
tc -= j;
}
if (tc) {c[++idx] = tc*ta; val[idx] = tc*tb;}
}
for (int i = 1; i <= idx; ++i)
for (int j = m; j >= c[i]; --j)
dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
printf("%d\n", dp[m]);
return 0;
}
https://www.luogu.com.cn/problem/P2623
- 01背包（价值由体积的函数值决定的背包）
- 完全背包
- 多重背包混合
#include <iostream>
using namespace std;
const int maxn = 2e3+9;
int n, m, dp[maxn], tp[maxn], val[maxn], c[maxn], num[maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", tp+i);
if (tp[i] == 2) scanf("%d%d%d", val+i, c+i, num+i);
else scanf("%d%d", val+i, c+i);
}
for (int i = 1; i <= n; ++i) {
if (tp[i] == 1) {
for (int j = m; j >= 1; --j) dp[j] = max(dp[j], val[i]*j*j-c[i]*j);
} else if (tp[i] == 2) {
for (int j = m; j >= c[i]; --j)
for (int k = 1; k <= num[i] && k*c[i] <= j; ++k)
dp[j] = max(dp[j], dp[j-k*c[i]]+k*val[i]);
} else {
for (int j = c[i]; j <= m; ++j) dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
}
}
printf("%d\n", dp[m]);
return 0;
}
组合背包
https://www.luogu.com.cn/problem/P1757
题目大意：就是普通01背包，但是给每个物品都添加了自己所属的组别。
1、此时遍历所有物品的话，就要按照组别->每个组别所包含的物品来遍历。
2、组别的目的就是加约束，每一组最多多少个，限制一个的话，可以通过把最内层遍历为该组别的遍历，中间设置为容量的遍历
for 所有组别
for 容量从最大到0
for 该组别中的所有物品
if 当前容量大于该物品的容量
AC代码：
#include <iostream>
using namespace std;
const int maxn = 1010;
int dp[maxn], c[maxn], v[maxn], grp[maxn][maxn], cnt[maxn]; // grp[i][j]表示第i组，第j个商品在总的索引里边的位次
int ctotal, n, tc, tval, tgrp, grpmax;
int main() {
scanf("%d%d", &ctotal, &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", c+i, v+i, &tgrp);
grpmax = max(grpmax, tgrp);
cnt[tgrp]++;
grp[tgrp][cnt[tgrp]] = i;
}
for (int i = 1; i <= grpmax; ++i)
for (int j = ctotal; j >= 0; --j)
for (int k = 1; k <= cnt[i]; ++k)
if (j-c[grp[i][k]]>=0) dp[j] = max(dp[j], dp[j-c[grp[i][k]]]+v[grp[i][k]]);
printf("%d\n", dp[ctotal]);
return 0;
}
多维代价 // 多维目的 – 背包
二维代价，一个目的
https://www.luogu.com.cn/problem/P1855
多（2）维代价，所以各自的dp数组都是2个维度
一个目的，所以只需要开一个dp数组来作为目的
1、dp[]数组遍历的就是代价元素，所以有几个代价，就增加几个维度，二维就是dp[代价1][代价2]，三维就是dp[代价1][代价2][代价3]
2、本题dp[i][j]表示在代价1为i，代价2位j的时候，所获的的最大的数量。
#include <iostream>
using namespace std;
#define maxn 205
int n, m, t, c_m[maxn], c_t[maxn], dp[maxn][maxn];
int main() {
scanf("%d%d%d", &n, &m, &t);
for (int i = 1; i <= n; ++i) scanf("%d%d", &c_m[i], &c_t[i]);
for (int i = 1; i <= n; ++i)
for (int j = m; j >= c_m[i] ; --j)
for (int k = t; k >= c_t[i]; --k)
dp[j][k] = max(dp[j][k], dp[j-c_m[i]][k-c_t[i]]+1);
printf("%d\n", dp[m][t]);
return 0;
}
https://www.luogu.com.cn/problem/P1507
同上，只不过通过添加了val来求最大值，而上面只是最大数量，val默认是1.
scanf("%d%d%d", &v, &m, &n);
for (int i = 1; i <= n; ++i) scanf("%d%d%d", &c_v[i], &c_m[i], &val[i]);
for (int i = 1; i <= n; ++i)
for (int j = v; j >= c_v[i]; --j)
for (int k = m; k >= c_m[i]; --k)
dp[j][k] = max(dp[j][k], dp[j-c_v[i]][k-c_m[i]]+val[i]);
printf("%d\n", dp[v][m]);
二维代价，两个目的
https://www.luogu.com.cn/problem/P1509
多（2）维代价，所以各自的dp数组都是2个维度
两个目的，要开两个dp数组来作为目的
#include <iostream>
using namespace std;
const int maxn = 105;
int n, rmb[maxn], rp[maxn], tim[maxn], totalRmb, totalRp; // 两个代价
int dpNum[maxn][maxn], dpTime[maxn][maxn]; // 两个目的
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d%d", rmb+i, rp+i, tim+i);
scanf("%d%d", &totalRmb, &totalRp);
for (int i = 1; i <= n; ++i)
for (int j = totalRmb; j >= rmb[i]; --j)
for (int k = totalRp; k >= rp[i]; --k)
if (dpNum[j][k] < dpNum[j-rmb[i]][k-rp[i]]+1) {
dpNum[j][k] = dpNum[j-rmb[i]][k-rp[i]]+1;
dpTime[j][k] = dpTime[j-rmb[i]][k-rp[i]]+tim[i];
} else if (dpNum[j][k] == dpNum[j-rmb[i]][k-rp[i]]+1)
dpTime[j][k] = min(dpTime[j][k], dpTime[j-rmb[i]][k-rp[i]]+tim[i]);
printf("%d\n", dpTime[totalRmb][totalRp]);
return 0;
}