1.01背包01背包就是指每件物品最多选1次有体积、价值背包容量是V求最大价值的问题它的核心写法就是把容量倒序遍历for(i 物品) for(jV;jv[i];j--) dp[j]max(dp[j], dp[j‑v[i]]w[i]);我们先看01背包的一道特别经典的例题有N NN件物品和一个容量是V VV的背包。每件物品只能使用一次。第i ii件物品的体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行两个整数N V NVNV用空格隔开分别表示物品数量和背包容积。接下来有N NN行每行两个整数v i , w i v_i, w_ivi,wi用空格隔开分别表示第i ii件物品的体积和价值。输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 1000 0 \lt N, V \le 10000N,V≤10000 v i , w i ≤ 1000 0\lt v_i, w_i \le 10000vi,wi≤1000输入样例4 5 1 2 2 4 3 4 4 5输出样例8对于这种题我们的核心解法就是选和不选对于每一次遍历都比较选择和不选这个物品所能达到的最大价值但是必须要注意倒序遍历以避免对单个物体进行重复取用我们看一下代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n ll dp[1010]; // 一维DP数组dp[j]表示体积j时的最大价值 void solve() { ll n, m; // n:物品数量m:背包容量 cin n m; for (ll i 1; i n; i) { // 遍历每件物品 ll v, w; // 当前物品的体积、价值 cin v w; // 逆序遍历背包容量避免同一物品被重复选择0-1背包核心 for (ll j m; j v; --j) { // 状态转移选不选当前物品 v 取最大值 dp[j] max(dp[j], dp[j - v] w); } } cout dp[m] endl; // 输出容量m时的最大价值 } signed main() { IOS; ll t 1; while (t--) solve(); return 0; }2.完全背包完全背包与上面的01背包只有一个不同点就是完全背包中每件物品都可以无限次取用。相比于01背包的倒序遍历防止一个物品被多次取用我们完全背包就用正序排序保证每个物品多次取用完全背包状态转移核心逻辑对于第i种物品体积v价值w有两种选择不选dp[j]保持原值继承之前的最大价值。选若选 1 个该物品那么剩余容量j-v的最大价值是dp[j-v]总价值为dp[j-v] w。由于可无限选需要正序遍历容量与 0-1 背包的逆序遍历不同保证同一物品能被多次选择。这么说正序可能有点不好理解我们举一个例子物品 v2,w3V5 j 从 2→5j2dp[2]max(dp[2],dp[0]3)→拿 1 次j4dp[4]max(dp[4],dp[2]3)→这里 dp [2] 已经拿过该物品于是又拿一次一共拿两件。我们区分01背包和完全背包只需要记住正序 允许重复使用当前物品倒序 禁止重复使用当前物品。includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n ll dp[1010]; // 一维DP数组dp[j]表示容量j时的最大价值 void solve() { ll n, m; // n:物品种数m:背包容量 cin n m; for (ll i 1; i n; i) { // 遍历每一种物品 ll v, w; // 当前物品的体积、价值 cin v w; // 正序遍历容量允许同一物品被选多次完全背包核心 for (ll j v; j m; j) { // 状态转移选当前物品可重复选取最大值 dp[j] max(dp[j], dp[j - v] w); } } cout dp[m] endl; // 输出容量m时的最大价值 } signed main() { IOS; ll t 1; while (t--) solve(); return 0; }3.多重背包多重背包其实就是指每件物品最多选s件的问题根据数据范围的不同有三种解法1.暴力解法这个一般只适用于解决数据范围不超过100的题像这道例题有N NN种物品和一个容量是V VV的背包。第i ii种物品最多有s i s_isi件每件体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数N V NVNV用空格隔开分别表示物品种数和背包容积。接下来有N NN行每行三个整数v i , w i , s i v_i, w_i, s_ivi,wi,si用空格隔开分别表示第i ii种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 100 0 \lt N, V \le 1000N,V≤1000 v i , w i , s i ≤ 100 0 \lt v_i, w_i, s_i \le 1000vi,wi,si≤100输入样例4 5 1 2 3 2 4 1 3 4 3 4 5 2输出样例10由于数据范围较小可以直接三重循环进行操作由于这些物品的个数是有限的因此可以选择1,2,3一直到s个为此可以在01背包的基础上进行修改在中间再多套一个循环来进行数量的选取就相当于01背包只有0和1的决策而多重背包有0到s1的决策for(ll i1;in;i) { ll v,w,s; cinvws; for(ll jm;jv;j--)//选择当前物品 for(ll k1;ksk*vj;k)//可选择的个数j-k*v0 dp[j]max(dp[j],dp[j-k*v]k*w); }完整代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define pii pairll,ll #define fi first #define se second const ll N1e610; ll dp[1100]; void solve() { ll n,m; cinnm; for(ll i1;in;i) { ll v,w,s; cinvws; for(ll jm;jv;j--) for(ll k1;ksk*vj;k) dp[j]max(dp[j],dp[j-k*v]k*w); } coutdp[m]endl; } signed main() { IOS; ll t1; // cint; while(t--) solve(); return 0; }2.二进制优化这个与暴力解法不同的点在于数据范围0 N ≤ 1000 0 \lt N \le 10000N≤10000 V ≤ 2000 0 \lt V \le 20000V≤20000 v i , w i , s i ≤ 2000 0 \lt v_i, w_i, s_i \le 20000vi,wi,si≤2000对于这个数据范围来说如果我们还进行三重循环一定会超时所以我们就想到把s变为2的幂次方的和其实简单来说就是把s件拆成若干组每组当作一件新物品转化成普通 01 背包。 比如 s5拆成1,2,21225。可以组合出 0‑5 任意件数。#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; void solve() { int n,m; cinnm; vectorintdp(m1,0); // dp[j]表示容量j的背包最大价值全部初始化为0 for(int i0;in;i){ // 循环处理每一类物品 int v,w,s; cinvws; // v单件体积w单件价值s该物品最多s件 for(int k1;ks;k*2){ // 二进制拆分k取1,2,4,8... s-k; // 拆分出去k件剩余数量s减去k int nvk*v; // 这一组虚拟物品的总体积 int nwk*w; // 这一组虚拟物品的总价值 for(int jm;jnv;j--){// 01背包倒序遍历防止重复选取 dp[j]max(dp[j],dp[j-nv]nw); // 不选 / 选该组虚拟物品取最大值 } } if(s0){ // 二进制循环结束后还有剩余件数 int nvs*v; // 剩余部分打包成一组虚拟物品体积 int nws*w; // 剩余部分打包成一组虚拟物品价值 for(int jm;jnv;j--){// 同样做01背包倒序更新 dp[j]max(dp[j],dp[j-nv]nw); } } } coutdp[m]; // 输出背包容量m下的最大价值 } signed main() { IOS; ll T1; while(T--) solve(); return 0; }3.单调队列优化这个与前面的区别还是在于数据范围0 N ≤ 1000 0 \lt N \le 10000N≤10000 V ≤ 20000 0 \lt V \le 200000V≤200000 v i , w i , s i ≤ 20000 0 \lt v_i, w_i, s_i \le 200000vi,wi,si≤20000这一题经过提示可知要利用到单调队列来进行优化由于这题相比上一题数据范围又大了一些利用二进制优化也过不了为此又有一种新的优化方法就是利用单调队列进行优化一件物品单件占体积 v单件价值 w最多拿 s 件。对于背包容量 j 我们可以拿 0 件、1 件、2 件 …… 最多 s 件同时拿的总体积不能超过 j。 拿 t 件时消耗体积(t * v)剩下背包容量(j - t*v)获得总价值旧状态价值 (t* w)dp [j] 所有合法 t 里面能得到的最大价值。我们这道题主要运用的就是余数分组加单调队列的思想把所有背包容量按照「除以 v 之后的余数」分成 v 组。 同一组里面所有数字都可以写成r k * vr余数固定不变k倍数0,1,2,3…同一组内部想从旧状态变到当前状态 从旧的倍数 t到现在倍数 k。 多拿 k-t件物品不能超过 s 件也就是0k-ts。旧状态是处理这个物品之前的结果记为 pre。 当前总价值 pre [r t*v] (k‑t)*w把式子拆开pre[rt*v](k-t)*w(pre[rt*v]-t*w)k*w对于现在这个 kk*w是固定不变的数。 括号里面这一部分只和 t 有关我们要在合法 t 里面找括号部分的最大值。问题转化随着 k 不断往后走有一个滑动窗口窗口里面装合法的 t求括号部分的最大值用单调队列维护。队列存 t倍数不存计算出来的括号值需要的时候现场算。如果窗口里某个 t 离现在 k 太远拿的件数超过 s直接扔掉。队列保持括号里的值从队头到队尾越来越小队头就是最大值。拿队头算出价值更新 dp再把当前 k 放进队列。pre 数组作用只使用处理该物品之前的旧结果避免重复无限拿物品。看一下代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n const int MAXV 20010; int dp[MAXV]; // dp[j]背包容量j的最大价值 int q[MAXV]; // 单调队列存放倍数k不是容量不是val值 void solve() { int n,m; cin n m; memset(dp, 0, sizeof(dp)); // dp数组全部初始化为0 for(int i 0; i n; i) { int v,w,s; cin v w s; int pre[MAXV]; memcpy(pre, dp, sizeof pre); // pre保存处理当前物品之前dp的快照只用旧状态转移 for(int r 0; r v; r) // r是容量对v取模的余数按余数分成v组每组独立算 { int head 0, tail -1; // head队头下标tail队尾下标tail-1代表队列为空 // k是组内倍数pos r k*v 得到真实背包容量 for(int k 0; r k * v m; k) { int pos r k * v; // pos等价于背包容量j // 窗口约束k-q[head]代表新增拿的物品件数超过s件就把队头过期状态弹出 while(head tail k - q[head] s) { head ; } // 队列不为空队头就是窗口内最优的历史倍数t if(head tail) { int t q[head]; // pre[rt*v] (k‑t)*w旧状态再拿k‑t件当前物品dp[pos]是不拿当前物品的旧值 dp[pos] max(dp[pos], pre[r t * v] (k - t) * w); } // val(x)pre[rx*v] - x*w新k的val更大队尾元素没有价值删掉队尾维持单调递减 while(head tail (pre[r k * v] - k * w) (pre[r q[tail] * v] - q[tail] * w)) { tail --; } q[tail] k; // 将当前倍数k存入队列队尾 } } } cout dp[m] endl; } signed main() { IOS; int T 1; while(T--) { solve(); } return 0; }4.混合背包其实混合背包就是01背包、完全背包、多重背包的结合版他的题目一般都是有三类物品物品一共有三类第一类物品只能用1次01背包第二类物品可以用无限次完全背包第三类物品最多只能用 si 次多重背包且一般si−1表示第 i 种物品只能用1次si0 表示第 i 种物品可以用无限次si0 表示第 i 种物品可以使用 si 次其余条件与其他背包没什么不同所以对于混合背包的解法我们就可以分为三部分先判断si的值如果si-1就用01背包模板解题如果si0就用完全背包si0就用多重背包这个混合背包特别直观原理相当于前面三种背包的结合我就不多赘述了直接看代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; void solve() { int n,m; cinnm; int dp[20010]; memset(dp,0,sizeof dp); for(int i0;in;i){ int v,w,s; cinvws; if(s-1){ for(int jm;jv;j--){ dp[j]max(dp[j],dp[j-v]w); } } else if(s0){ for(int jv;jm;j){ dp[j]max(dp[j],dp[j-v]w); } } else{ for(int k1;ks;k*2){ s-k; int nvk*v; int nwk*w; for(int jm;jnv;j--){ dp[j]max(dp[j],dp[j-nv]nw); } } if(s0){ int nvs*v; int nws*w; for(int jm;jnv;j--){ dp[j]max(dp[j],dp[j-nv]nw); } } } } coutdp[m]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }5.二维费用背包二维费用背包其实根本还是01背包只不过比01背包多了一个重量的条件就像这道题目8. 二维费用的背包问题 - AcWing题库这道题解法与01背包相同都是用倒序找到最优解,只需要在01背包的容积倒序基础上再加上质量倒序。看代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; int dp[1010][1010]; void solve() { int n,V,M; cinnVM; for(int i0;in;i){ int v1,v2,w; cinv1v2w; for(int jV;jv1;j--){ for(int kM;kv2;k--){ dp[j][k]max(dp[j][k],dp[j-v1][k-v2]w); } } } coutdp[V][M]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }6.分组背包分组背包其实还是01背包的变形都是只能选一个但是分组背包是指能选一组物品中的一个使最终结果最优9. 分组背包问题 - AcWing题库这道题就是在01背包基础上加了一个分组的条件限制就是在每组中找到最优物品使得背包价值最大#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; int dp[1005]; //dp[k]代表背包容量k能装的最大价值 int v[105],w[105]; //v体积 w价值 void solve() { int n,V; cinnV; //n是组的数量V背包总容量 for(int i0;in;i){ //循环每一组物品 int s; cins; //s代表当前这一组里面有s个物品 for(int j1;js;j) cinv[j]w[j]; //读入本组s个物品存到v[1]~v[s],w[1]~w[s] //分组背包倒序枚举背包容量防止重复选同一组多个 for(int kV;k0;k--){ //遍历本组全部s件物品尝试选其中一件 for(int l1;ls;l){ if(kv[l]){ //当前容量k装得下第l号物品 //不选dp[k]选本组l物品dp[k‑v[l]]w[l]取更大值 dp[k]max(dp[k],dp[k-v[l]]w[l]); } } } } coutdp[V]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }7.有依赖的背包问题先看一下题目10. 有依赖的背包问题 - AcWing题库这个在背包问题里面算是比较难理解的点因为它牵扯上了树属于树形背包所以我们必须要考虑树形结构父子节点之间的连接对于这种背包题目给我们限制如果我们选择了一个物品那么它的父节点的物品我们也必须选择有点类似于分组背包吧但是又有很大不同我们如果要选择子节点就必须选择它的父节点那么我们就容易想到这道题最好用递归从子节点向上递推直到达到最优解。#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; ll dp[105][105]; //dp[u][j]u的子树花费体积j必须选u的最大价值 vectorintson[105];//son[u]保存u的所有子节点 ll n,V; //n物品数V背包总容量 ll v[105],w[105]; //v[i]物品i体积w[i]物品i价值 void dfs(int u){ //初始化只选u自己不选任何子节点 for(int jV;jv[u];j--){ dp[u][j]w[u]; } //遍历u的每一个子节点s for(int s:son[u]){ dfs(s); //递归先把子树s的dp全部算好 //分组背包合并子树j倒序防止重复选取同一个子树 for(int jV;jv[u];j--){ //k分配给子树s的体积k从1开始k最多j‑v[u]u本身占v[u] for(int k1;kj-v[u];k){ //j‑k留给u以及之前已经合并完的子树k给当前子树s dp[u][j]max(dp[u][j],dp[u][j-k]dp[s][k]); } } } } void solve() { cinnV; ll root0; //虚拟根节点0所有真正根挂在0下面 for(int i1;in;i){ ll p; cinv[i]w[i]p; //读入体积、价值、父节点p if(p-1){ //原树的根挂到虚拟根0的儿子列表 son[0].push_back(i); } else{ //i的父是p加入p的子节点 son[p].push_back(i); } } dfs(root); //从虚拟根0开始dfs coutdp[root][V]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }8.背包问题求具体方案这道题其实还是01背包就是要求能达到最大价值的方案中字典序最小的方案12. 背包问题求具体方案 - AcWing题库这道题要求最小字典序就要倒过来dp,从n号商品遍历到1号商品我们先设dp[i][j]:表示只考虑物品i~n,背包容量j的最大价值然后从后往前遍历回溯的时候优先选择编号小的物品原理公式不选 idp[i][j] dp[i1][j]选 ijv [i]dp[i][j] dp[i1][j‑v[i]] w[i]取 max。#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; ll v[2000],w[2000]; //v[i]第i件物品体积w[i]第i件物品价值 ll dp[2000][2000]; //dp[i][j]只使用 i~n 的物品背包容量j的最大价值 void solve() { ll n,m; cinnm; //n物品总数m背包总容量 for(int i1;in;i){ cinv[i]w[i]; //读入每件物品的体积、价值 } //i从后往前倒推状态是i~n物品 for(int in;i1;i--){ //枚举所有背包容量0~m for(int j0;jm;j){ dp[i][j]dp[i1][j]; //情况1不选第i件物品继承i1~n的结果 if(jv[i]){ //背包容量j装得下i号物品 //情况2选i号物品i的价值 i1~n在剩余j‑v[i]容量下的最优取max dp[i][j]max(dp[i][j],dp[i1][j-v[i]]w[i]); } } } //回溯i从小到大优先选小编号得到字典序最小的选法 for(int i1;in;i){ //当前剩余容量m装得下i并且选i可以达到当前局面最优解 if(mv[i]dp[i][m]dp[i1][m-v[i]]w[i]){ couti ; //选中i输出物品编号 m-v[i]; //剩余背包容量减去i的体积 } } } signed main() { IOS; ll T1; while(T--) solve(); return 0; }
背包九讲—全解析（详细）
1.01背包01背包就是指每件物品最多选1次有体积、价值背包容量是V求最大价值的问题它的核心写法就是把容量倒序遍历for(i 物品) for(jV;jv[i];j--) dp[j]max(dp[j], dp[j‑v[i]]w[i]);我们先看01背包的一道特别经典的例题有N NN件物品和一个容量是V VV的背包。每件物品只能使用一次。第i ii件物品的体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行两个整数N V NVNV用空格隔开分别表示物品数量和背包容积。接下来有N NN行每行两个整数v i , w i v_i, w_ivi,wi用空格隔开分别表示第i ii件物品的体积和价值。输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 1000 0 \lt N, V \le 10000N,V≤10000 v i , w i ≤ 1000 0\lt v_i, w_i \le 10000vi,wi≤1000输入样例4 5 1 2 2 4 3 4 4 5输出样例8对于这种题我们的核心解法就是选和不选对于每一次遍历都比较选择和不选这个物品所能达到的最大价值但是必须要注意倒序遍历以避免对单个物体进行重复取用我们看一下代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n ll dp[1010]; // 一维DP数组dp[j]表示体积j时的最大价值 void solve() { ll n, m; // n:物品数量m:背包容量 cin n m; for (ll i 1; i n; i) { // 遍历每件物品 ll v, w; // 当前物品的体积、价值 cin v w; // 逆序遍历背包容量避免同一物品被重复选择0-1背包核心 for (ll j m; j v; --j) { // 状态转移选不选当前物品 v 取最大值 dp[j] max(dp[j], dp[j - v] w); } } cout dp[m] endl; // 输出容量m时的最大价值 } signed main() { IOS; ll t 1; while (t--) solve(); return 0; }2.完全背包完全背包与上面的01背包只有一个不同点就是完全背包中每件物品都可以无限次取用。相比于01背包的倒序遍历防止一个物品被多次取用我们完全背包就用正序排序保证每个物品多次取用完全背包状态转移核心逻辑对于第i种物品体积v价值w有两种选择不选dp[j]保持原值继承之前的最大价值。选若选 1 个该物品那么剩余容量j-v的最大价值是dp[j-v]总价值为dp[j-v] w。由于可无限选需要正序遍历容量与 0-1 背包的逆序遍历不同保证同一物品能被多次选择。这么说正序可能有点不好理解我们举一个例子物品 v2,w3V5 j 从 2→5j2dp[2]max(dp[2],dp[0]3)→拿 1 次j4dp[4]max(dp[4],dp[2]3)→这里 dp [2] 已经拿过该物品于是又拿一次一共拿两件。我们区分01背包和完全背包只需要记住正序 允许重复使用当前物品倒序 禁止重复使用当前物品。includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n ll dp[1010]; // 一维DP数组dp[j]表示容量j时的最大价值 void solve() { ll n, m; // n:物品种数m:背包容量 cin n m; for (ll i 1; i n; i) { // 遍历每一种物品 ll v, w; // 当前物品的体积、价值 cin v w; // 正序遍历容量允许同一物品被选多次完全背包核心 for (ll j v; j m; j) { // 状态转移选当前物品可重复选取最大值 dp[j] max(dp[j], dp[j - v] w); } } cout dp[m] endl; // 输出容量m时的最大价值 } signed main() { IOS; ll t 1; while (t--) solve(); return 0; }3.多重背包多重背包其实就是指每件物品最多选s件的问题根据数据范围的不同有三种解法1.暴力解法这个一般只适用于解决数据范围不超过100的题像这道例题有N NN种物品和一个容量是V VV的背包。第i ii种物品最多有s i s_isi件每件体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数N V NVNV用空格隔开分别表示物品种数和背包容积。接下来有N NN行每行三个整数v i , w i , s i v_i, w_i, s_ivi,wi,si用空格隔开分别表示第i ii种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 100 0 \lt N, V \le 1000N,V≤1000 v i , w i , s i ≤ 100 0 \lt v_i, w_i, s_i \le 1000vi,wi,si≤100输入样例4 5 1 2 3 2 4 1 3 4 3 4 5 2输出样例10由于数据范围较小可以直接三重循环进行操作由于这些物品的个数是有限的因此可以选择1,2,3一直到s个为此可以在01背包的基础上进行修改在中间再多套一个循环来进行数量的选取就相当于01背包只有0和1的决策而多重背包有0到s1的决策for(ll i1;in;i) { ll v,w,s; cinvws; for(ll jm;jv;j--)//选择当前物品 for(ll k1;ksk*vj;k)//可选择的个数j-k*v0 dp[j]max(dp[j],dp[j-k*v]k*w); }完整代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define pii pairll,ll #define fi first #define se second const ll N1e610; ll dp[1100]; void solve() { ll n,m; cinnm; for(ll i1;in;i) { ll v,w,s; cinvws; for(ll jm;jv;j--) for(ll k1;ksk*vj;k) dp[j]max(dp[j],dp[j-k*v]k*w); } coutdp[m]endl; } signed main() { IOS; ll t1; // cint; while(t--) solve(); return 0; }2.二进制优化这个与暴力解法不同的点在于数据范围0 N ≤ 1000 0 \lt N \le 10000N≤10000 V ≤ 2000 0 \lt V \le 20000V≤20000 v i , w i , s i ≤ 2000 0 \lt v_i, w_i, s_i \le 20000vi,wi,si≤2000对于这个数据范围来说如果我们还进行三重循环一定会超时所以我们就想到把s变为2的幂次方的和其实简单来说就是把s件拆成若干组每组当作一件新物品转化成普通 01 背包。 比如 s5拆成1,2,21225。可以组合出 0‑5 任意件数。#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; void solve() { int n,m; cinnm; vectorintdp(m1,0); // dp[j]表示容量j的背包最大价值全部初始化为0 for(int i0;in;i){ // 循环处理每一类物品 int v,w,s; cinvws; // v单件体积w单件价值s该物品最多s件 for(int k1;ks;k*2){ // 二进制拆分k取1,2,4,8... s-k; // 拆分出去k件剩余数量s减去k int nvk*v; // 这一组虚拟物品的总体积 int nwk*w; // 这一组虚拟物品的总价值 for(int jm;jnv;j--){// 01背包倒序遍历防止重复选取 dp[j]max(dp[j],dp[j-nv]nw); // 不选 / 选该组虚拟物品取最大值 } } if(s0){ // 二进制循环结束后还有剩余件数 int nvs*v; // 剩余部分打包成一组虚拟物品体积 int nws*w; // 剩余部分打包成一组虚拟物品价值 for(int jm;jnv;j--){// 同样做01背包倒序更新 dp[j]max(dp[j],dp[j-nv]nw); } } } coutdp[m]; // 输出背包容量m下的最大价值 } signed main() { IOS; ll T1; while(T--) solve(); return 0; }3.单调队列优化这个与前面的区别还是在于数据范围0 N ≤ 1000 0 \lt N \le 10000N≤10000 V ≤ 20000 0 \lt V \le 200000V≤200000 v i , w i , s i ≤ 20000 0 \lt v_i, w_i, s_i \le 200000vi,wi,si≤20000这一题经过提示可知要利用到单调队列来进行优化由于这题相比上一题数据范围又大了一些利用二进制优化也过不了为此又有一种新的优化方法就是利用单调队列进行优化一件物品单件占体积 v单件价值 w最多拿 s 件。对于背包容量 j 我们可以拿 0 件、1 件、2 件 …… 最多 s 件同时拿的总体积不能超过 j。 拿 t 件时消耗体积(t * v)剩下背包容量(j - t*v)获得总价值旧状态价值 (t* w)dp [j] 所有合法 t 里面能得到的最大价值。我们这道题主要运用的就是余数分组加单调队列的思想把所有背包容量按照「除以 v 之后的余数」分成 v 组。 同一组里面所有数字都可以写成r k * vr余数固定不变k倍数0,1,2,3…同一组内部想从旧状态变到当前状态 从旧的倍数 t到现在倍数 k。 多拿 k-t件物品不能超过 s 件也就是0k-ts。旧状态是处理这个物品之前的结果记为 pre。 当前总价值 pre [r t*v] (k‑t)*w把式子拆开pre[rt*v](k-t)*w(pre[rt*v]-t*w)k*w对于现在这个 kk*w是固定不变的数。 括号里面这一部分只和 t 有关我们要在合法 t 里面找括号部分的最大值。问题转化随着 k 不断往后走有一个滑动窗口窗口里面装合法的 t求括号部分的最大值用单调队列维护。队列存 t倍数不存计算出来的括号值需要的时候现场算。如果窗口里某个 t 离现在 k 太远拿的件数超过 s直接扔掉。队列保持括号里的值从队头到队尾越来越小队头就是最大值。拿队头算出价值更新 dp再把当前 k 放进队列。pre 数组作用只使用处理该物品之前的旧结果避免重复无限拿物品。看一下代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n const int MAXV 20010; int dp[MAXV]; // dp[j]背包容量j的最大价值 int q[MAXV]; // 单调队列存放倍数k不是容量不是val值 void solve() { int n,m; cin n m; memset(dp, 0, sizeof(dp)); // dp数组全部初始化为0 for(int i 0; i n; i) { int v,w,s; cin v w s; int pre[MAXV]; memcpy(pre, dp, sizeof pre); // pre保存处理当前物品之前dp的快照只用旧状态转移 for(int r 0; r v; r) // r是容量对v取模的余数按余数分成v组每组独立算 { int head 0, tail -1; // head队头下标tail队尾下标tail-1代表队列为空 // k是组内倍数pos r k*v 得到真实背包容量 for(int k 0; r k * v m; k) { int pos r k * v; // pos等价于背包容量j // 窗口约束k-q[head]代表新增拿的物品件数超过s件就把队头过期状态弹出 while(head tail k - q[head] s) { head ; } // 队列不为空队头就是窗口内最优的历史倍数t if(head tail) { int t q[head]; // pre[rt*v] (k‑t)*w旧状态再拿k‑t件当前物品dp[pos]是不拿当前物品的旧值 dp[pos] max(dp[pos], pre[r t * v] (k - t) * w); } // val(x)pre[rx*v] - x*w新k的val更大队尾元素没有价值删掉队尾维持单调递减 while(head tail (pre[r k * v] - k * w) (pre[r q[tail] * v] - q[tail] * w)) { tail --; } q[tail] k; // 将当前倍数k存入队列队尾 } } } cout dp[m] endl; } signed main() { IOS; int T 1; while(T--) { solve(); } return 0; }4.混合背包其实混合背包就是01背包、完全背包、多重背包的结合版他的题目一般都是有三类物品物品一共有三类第一类物品只能用1次01背包第二类物品可以用无限次完全背包第三类物品最多只能用 si 次多重背包且一般si−1表示第 i 种物品只能用1次si0 表示第 i 种物品可以用无限次si0 表示第 i 种物品可以使用 si 次其余条件与其他背包没什么不同所以对于混合背包的解法我们就可以分为三部分先判断si的值如果si-1就用01背包模板解题如果si0就用完全背包si0就用多重背包这个混合背包特别直观原理相当于前面三种背包的结合我就不多赘述了直接看代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; void solve() { int n,m; cinnm; int dp[20010]; memset(dp,0,sizeof dp); for(int i0;in;i){ int v,w,s; cinvws; if(s-1){ for(int jm;jv;j--){ dp[j]max(dp[j],dp[j-v]w); } } else if(s0){ for(int jv;jm;j){ dp[j]max(dp[j],dp[j-v]w); } } else{ for(int k1;ks;k*2){ s-k; int nvk*v; int nwk*w; for(int jm;jnv;j--){ dp[j]max(dp[j],dp[j-nv]nw); } } if(s0){ int nvs*v; int nws*w; for(int jm;jnv;j--){ dp[j]max(dp[j],dp[j-nv]nw); } } } } coutdp[m]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }5.二维费用背包二维费用背包其实根本还是01背包只不过比01背包多了一个重量的条件就像这道题目8. 二维费用的背包问题 - AcWing题库这道题解法与01背包相同都是用倒序找到最优解,只需要在01背包的容积倒序基础上再加上质量倒序。看代码#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; int dp[1010][1010]; void solve() { int n,V,M; cinnVM; for(int i0;in;i){ int v1,v2,w; cinv1v2w; for(int jV;jv1;j--){ for(int kM;kv2;k--){ dp[j][k]max(dp[j][k],dp[j-v1][k-v2]w); } } } coutdp[V][M]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }6.分组背包分组背包其实还是01背包的变形都是只能选一个但是分组背包是指能选一组物品中的一个使最终结果最优9. 分组背包问题 - AcWing题库这道题就是在01背包基础上加了一个分组的条件限制就是在每组中找到最优物品使得背包价值最大#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; int dp[1005]; //dp[k]代表背包容量k能装的最大价值 int v[105],w[105]; //v体积 w价值 void solve() { int n,V; cinnV; //n是组的数量V背包总容量 for(int i0;in;i){ //循环每一组物品 int s; cins; //s代表当前这一组里面有s个物品 for(int j1;js;j) cinv[j]w[j]; //读入本组s个物品存到v[1]~v[s],w[1]~w[s] //分组背包倒序枚举背包容量防止重复选同一组多个 for(int kV;k0;k--){ //遍历本组全部s件物品尝试选其中一件 for(int l1;ls;l){ if(kv[l]){ //当前容量k装得下第l号物品 //不选dp[k]选本组l物品dp[k‑v[l]]w[l]取更大值 dp[k]max(dp[k],dp[k-v[l]]w[l]); } } } } coutdp[V]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }7.有依赖的背包问题先看一下题目10. 有依赖的背包问题 - AcWing题库这个在背包问题里面算是比较难理解的点因为它牵扯上了树属于树形背包所以我们必须要考虑树形结构父子节点之间的连接对于这种背包题目给我们限制如果我们选择了一个物品那么它的父节点的物品我们也必须选择有点类似于分组背包吧但是又有很大不同我们如果要选择子节点就必须选择它的父节点那么我们就容易想到这道题最好用递归从子节点向上递推直到达到最优解。#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; ll dp[105][105]; //dp[u][j]u的子树花费体积j必须选u的最大价值 vectorintson[105];//son[u]保存u的所有子节点 ll n,V; //n物品数V背包总容量 ll v[105],w[105]; //v[i]物品i体积w[i]物品i价值 void dfs(int u){ //初始化只选u自己不选任何子节点 for(int jV;jv[u];j--){ dp[u][j]w[u]; } //遍历u的每一个子节点s for(int s:son[u]){ dfs(s); //递归先把子树s的dp全部算好 //分组背包合并子树j倒序防止重复选取同一个子树 for(int jV;jv[u];j--){ //k分配给子树s的体积k从1开始k最多j‑v[u]u本身占v[u] for(int k1;kj-v[u];k){ //j‑k留给u以及之前已经合并完的子树k给当前子树s dp[u][j]max(dp[u][j],dp[u][j-k]dp[s][k]); } } } } void solve() { cinnV; ll root0; //虚拟根节点0所有真正根挂在0下面 for(int i1;in;i){ ll p; cinv[i]w[i]p; //读入体积、价值、父节点p if(p-1){ //原树的根挂到虚拟根0的儿子列表 son[0].push_back(i); } else{ //i的父是p加入p的子节点 son[p].push_back(i); } } dfs(root); //从虚拟根0开始dfs coutdp[root][V]; } signed main() { IOS; ll T1; while(T--) solve(); return 0; }8.背包问题求具体方案这道题其实还是01背包就是要求能达到最大价值的方案中字典序最小的方案12. 背包问题求具体方案 - AcWing题库这道题要求最小字典序就要倒过来dp,从n号商品遍历到1号商品我们先设dp[i][j]:表示只考虑物品i~n,背包容量j的最大价值然后从后往前遍历回溯的时候优先选择编号小的物品原理公式不选 idp[i][j] dp[i1][j]选 ijv [i]dp[i][j] dp[i1][j‑v[i]] w[i]取 max。#includebits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl \n #define fi firse #define se second const ll N1e610; ll v[2000],w[2000]; //v[i]第i件物品体积w[i]第i件物品价值 ll dp[2000][2000]; //dp[i][j]只使用 i~n 的物品背包容量j的最大价值 void solve() { ll n,m; cinnm; //n物品总数m背包总容量 for(int i1;in;i){ cinv[i]w[i]; //读入每件物品的体积、价值 } //i从后往前倒推状态是i~n物品 for(int in;i1;i--){ //枚举所有背包容量0~m for(int j0;jm;j){ dp[i][j]dp[i1][j]; //情况1不选第i件物品继承i1~n的结果 if(jv[i]){ //背包容量j装得下i号物品 //情况2选i号物品i的价值 i1~n在剩余j‑v[i]容量下的最优取max dp[i][j]max(dp[i][j],dp[i1][j-v[i]]w[i]); } } } //回溯i从小到大优先选小编号得到字典序最小的选法 for(int i1;in;i){ //当前剩余容量m装得下i并且选i可以达到当前局面最优解 if(mv[i]dp[i][m]dp[i1][m-v[i]]w[i]){ couti ; //选中i输出物品编号 m-v[i]; //剩余背包容量减去i的体积 } } } signed main() { IOS; ll T1; while(T--) solve(); return 0; }
)
