动态规划——背包问题全总结关于动态规划的背包问题可分为0/1 背包问题分组背包问题多重背包问题完全背包问题1 0/1背包问题问题描述有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输入描述第一行两个整数 N,V,用空格隔开分别表示物品数量和背包容积。接下来有 N 行每行两个数 vi,wi,用空格分隔开表示该物体的体积和价值。输出描述输出一个整数表示最大价值。分析引入一个 (N1)×(V1)(1)×(1) 的二维数组 dp[][][][]。dp[i][j][][] 表示把前 i 个物品【1,i1,】装入容量为 j 的背包中获得最大价值。把每个 dp[i][j][][] 都看做一个背包容量为 j装 1∼i1∼ 这些物品最后的 dp[N][V][][] 为问题答案。dp 转移方程第 i 个物品的体积比容量 j 还大不能装进背包。直接继承前 i−1−1 个物品装进容量为 j 的背包情况即可即dp[i][j]dp[i−1][j][][][−1][]第 i 个物品的体积比容量 j 小能装进背包又可以分成两种情况装或不装① 装第 i 个物品dp[i][j]dp[i−1][j−v[i]]w[i][][][−1][−[]][]② 不装第 i 个物品dp[i][j]dp[i−1][j][][][−1][]取两者的最大值dp[i][j]max(dp[i−1][j], dp[i−1][j−v[i]]w[i])[][]max([−1][], [−1][−[]][])递推代码暴力做法#include bits/stdc.h using namespace std; const int N 1010; int w[N], v[N]; // 物品的价值和体积 int dp[N][N]; int solve(int n, int V) { for (int i 1; i n; i) for (int j 0; j V; j) { if (v[i] j) dp[i][j] dp[i - 1][j]; // 第i个物品比背包大装不了 else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]); // 能装 } return dp[n][V]; } int main() { int n, V; scanf(%d%d, n, V); for (int i 1; i n; i) scanf(%d%d, v[i], w[i]); printf(%d, solve(n, V)); return 0; }记忆化搜索暴力做法#include bits/stdc.h using namespace std; const int N 1010; int w[N], v[N]; int dp[N][N]; int solve(int i, int j) { if (dp[i][j] ! 0) return dp[i][j]; if (i 0) return 0; int res; if (v[i] j) res solve(i - 1, j); else res max(solve(i - 1, j), solve(i - 1, j - v[i]) w[i]); return dp[i][j] res; } int main() { int n, V; scanf(%d%d, n, V); for (int i 1; i n; i) scanf(%d%d, v[i], w[i]); printf(%d, solve(n,V)); return 0; }滚动数组优化dp[i][][][] 只与 dp[i−1][][−1][] 有关与其他没有关系。使用覆盖有如下两种方式1.1 交替滚动定义 dp[2][j][2][]用 dp[0][ ][0][ ] 和 dp[1][ ][1][ ] 交替滚动。在如下代码中now 指向正在计算的最新一行old 指向已经计算过的旧的一行。在递推关系中now 相当于 iold 相当于 i−1−1。int dp[2][N]; int solve(int n, int V) { int now0,old1; for(int i1;in;i) { swap(old,now); // 交替转换 for(int j0;jV;j) { dp[now][j]dp[old][j]; if(v[i]j) dp[now][j]max(dp[old][j],dp[old][j-v[i]]w[i]); } } return dp[now][V]; // 返回最新的行 }完整代码#include bits/stdc.h using namespace std; int n, m; const int N 1010; int dp[2][N]; int v[N], w[N]; int main() { scanf(%d%d, m, n); for (int i 1; i n; i) scanf(%d%d, v[i], w[i]); int old 1, ne 0; for (int i 1; i n; i) { swap(old, ne); // 交替上一列与下一列 for (int j 1; j m; j) { dp[ne][j] dp[old][j]; // 将旧状态转移 if (v[i] j) dp[ne][j] max(dp[ne][j], dp[old][j - v[i]] w[i]); } } printf(%d, dp[ne][m]); // 输出新状态 return 0; }1.2 自我滚动原理和上述类似int dp[N]; int solve(int n,int V) { for(int i1;in;i) for(int jV;jv[i];j--) dp[j]max(dp[j],dp[j-v[i]]w[i]); return dp[V]; }完整代码#include bits/stdc.h using namespace std; int n, m; const int N 1010; int dp[N]; int v[N], w[N]; int main() { scanf(%d%d, m, n); for (int i 1; i n; i) scanf(%d%d, 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]); } // 自我滚动数组 printf(%d, dp[m]); return 0; }2 分组背包问题问题描述有 N 组物品和一个容量是 V 的背包。每组物品有若干个同一组内的物品最多只能选一个。每件物品的体积是 vik价值是 wik其中 i 是组号k 是组内编号。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输入描述第一行有两个整数 N,V,用空格隔开分别表示物品组数和背包容量。接下来有 N 组数据每组数据第一行有一个整数 Si表示第 i 个物品组的物品数量每组数据接下来有 Si 行每行有两个整数 vik,wik,用空格隔开分别表示第 i 个物品组的第 k 个物品的体积和价值。输出格式输出一个整数表示最大价值。分析定义一个状态 dp[i][j][][]表示把前 i 组的物品装进容量为 j 的背包每个组里最多选一个物品里可获得的最大价值。状态转移方程dp[i][j]max{dp[i−1][j], dp[i−1][j−v[i][k]]w[i][k]}[][]max{[−1][], [−1][−[][]][][]}其中 dp[i−1][j][−1][] 表示第 i 组不选择物品dp[i−1][j−v[i][k]][−1][−[][]] 表示第 i 组的第 k 个物品求解方程需要 i,j,k,, 三重循环。若改为滚动数组则状态转移方程为dp[j]max{dp[j], dp[j−v[i][k]]w[i][k]}[]max{[], [−[][]][][]}参考代码写法一#includebits/stdc.h using namespace std; const int N110; int n,m; int dp[N],v[N],w[N]; int main() { scanf(%d%d,n,m); for(int i0;in;i) { int num; // 第i1组的物品个数 scanf(%d,num); for(int j1;jnum;j) scanf(%d%d,v[j],w[j]); // 第i组num个物品的体积和价格 for(int jm;j0;j--) for(int k1;knum;k) if(jv[k]) dp[j]max(dp[j],dp[j-v[k]]w[k]); } printf(%d,dp[m]); return 0; }写法二#includebits/stdc.h using namespace std; const int N110; int v[N][N],w[N][N],num[N]; // v[i][j]第i组第j个物品的体积 // w[i][j]第i组第j个物品的价值 // num[i]第i组内物品个数 int dp[N]; int n,sum; int main() { cinnsum; for(int i1;in;i) { cinnum[i]; for(int j1;jnum[i];j) cinv[i][j]w[i][j]; } for(int i1;in;i) for(int jsum;j0;j--) for(int k0;knum[i];k) if(jv[i][k]) dp[j]max(dp[j],dp[j-v[i][k]]w[i][k]); coutdp[sum]; return 0; }3 多重背包问题问题描述有一个最大载重为 W 的采集车洞穴里总共有 n 种宝物每种宝物的价值为 vi重量为 wi每种宝物有 mi 件。希望在采集车不超载的前提下选择一些宝物装进采集车使得它们的价值和最大。输入描述第一行为一个整数 n 和 W分别表示宝物种数和采集车的最大载重。接下来 n 行每行三个整数 vi,wi,mi,,。输出描述输出最大宝物价值。分析将 m 件物品看成多个不同的物品转化成 0/1 背包问题。参考代码基础暴力版本三重循环时间一般会爆掉#include bits/stdc.h using namespace std; const int N 1010; int n, sum; // n为物品种类数sum为背包总体积 int dp[N], w[N], v[N], num[N]; // dp[i]容量i的最大价值 // w[i]第i个物品价值 // v[i]第i个物品体积 // num[i]第i个物品数量 int main() { cin n sum; for (int i 1; i n; i) cin v[i] w[i] num[i]; for (int i 1; i n; i) for (int j sum;j v[i]; j--) for (int k 1;j k * v[i]k num[i]; k) dp[j] max(dp[j], dp[j - v[i] * k] w[i] * k); cout dp[sum]; return 0; }二进制优化版本数学规律每个数都可以由以下部分来组成numan⋅2nan−1⋅2n−1⋯a1⋅2a0⋅2−1⋅2−1⋯1⋅20根据这个规律任意一个数可从 1,2,4,8…1,2,4,8… 以及一个多余项组成。每个数都可由二次幂升序排列的数来组成相比较 num 个数字其二进制表示可以大大降低时间复杂度。思路把二次幂升序和多余项看成一种物品的选择之后用 0/1 背包处理。#includebits/stdc.h using namespace std; const int N11010,M2010; int dp[M]; int v[N],w[N]; int n,sum; int main() { cinnsum; int all0; for(int i1;in;i) { int a,b,c; cinabc; for(int k1;kc;k*2) { all; v[all]a*k; w[all]b*k; c-k; } if(c0) { all; v[all]a*c; w[all]b*c; } } nall; for(int i1;in;i) for(int jsum;jv[i];j--) dp[j]max(dp[j],dp[j-v[i]]w[i]); coutdp[sum]; return 0; }4 完全背包问题问题描述现有 N 种物品和一个最多能承重 M 的背包每种物品都有无限个第 i 种物品的重量是 wi价值是 vi。在背包能承受的范围内试问将哪些物品装入背包后可使总价值最大求这个最大价值。分析思路一转化法把完全背包问题转化成多重背包问题因为物品虽然是无限个但能装进去的个数是有限多个。将能装进 11 个、22 个、33 个 …… 利用二进制优化来操作最后变成 0/1 背包问题。个人结合二进制优化思路非标准正解参考代码#include bits/stdc.h using namespace std; const int N 1010, M 11010; int v[M], w[M]; int dp[N]; int n, sum; int all; int main() { cin n sum; for (int i 1; i n; i) { int t; // 最多能放多少东西 int a, b; // a体积b价值 cin a b; t sum / a; for (int k 1; k t; k * 2) { // 二进制优化 all; v[all] a * k; w[all] b * k; t - k; } if (t 0) { // 处理多余项 all; v[all] a * t; w[all] b * t; } } n all; // 0/1背包 for (int i 1; i all; i) for (int j sum; j v[i]; j--) dp[j] max(dp[j], dp[j - v[i]] w[i]); cout dp[sum]; return 0; }思路二正解状态方程优化观察规律dp[2][5]max(dp[1][5], dp[1][3]w, dp[1][1]2w)dp[2][3]max(dp[1][3], dp[1][1]w)max(dp[1][3], dp[2][1]w)dp[2][5]max(dp[1][5], dp[2][3]w)[2][5]max([1][5], [1][3], [1][1]2)[2][3]max([1][3], [1][1])max([1][3], [2][1])[2][5]max([1][5], [2][3])由此得到优化转移方程