Loading... 本文给背包问题大致理出了一个框架,不会面面俱到,而定有不尽不详之处。 --- > 背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。 *摘自百度百科* 背包问题是DP问题中的一大类,其中又可大致分为以下几类。 ## 01背包 01背包是最基础的背包问题。一般化的01背包问题描述如下: 有N件物品和一个容量为M的背包。第i个物品的体积是$v_i$,价值是$w_i$。求选取这些物品 放入背包,能够得到的最大价值。 既然每种物品只有一件,那么对于每种物品就只有两种情况:取或不取。取,还要符合体积不大于背包剩余容量。可以得到状态转移方程 $$ F[i][j] = \left \{ \begin{array}{0} F[i-1][j-v_i]+w_i,j \ge v_i \\ F[i-1][j] \end{array} \right . $$ 得到DP代码 ```cpp for(int i = 0; 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]); ``` ### 01背包的空间优化 去掉f数组第一维,得到 $$ F[i][j] = \max(F[j-v_i]+w_i , F[j]) $$ ```cpp for(int i = 0; i < n; ++i) for(int j = m; j >= v[i]; --j) f[j] = max(f[j], f[j-v[i]]+w[i]); ``` 为什么可以压缩为一维?因为在动态规划的过程中,永远是一行和上一行之间的依赖关系。那么可以分配两行,循环使用。 ## 完全背包 > 题目 > > 有N种物品和一个容量为V的背包,每种物品都有无限件可用。 > > 第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。 *摘自百度百科* 枚举取每件物品的件数,并考虑背包剩余容量是否大于k件某种物品的代价和。那么可得到 $$ F[i][j]=\max\{F[i-1][j-k*v_i]+k*w_i\} , j \ge k*v_i $$ ### 题解 存钱罐 #### 题目 *题目有修改* ##### 描述 一天,某人收到了好友送给他的一个存钱罐。经过半年存款后,他已经存了不少钱,但是不知道这个存钱罐里有多少钱。已知存钱罐的初始重量和现在的重量,以及每种硬币的面额和重量。那么这个存钱罐里最少有多少钱呢? ##### 输入 第一行输入两个整数 e,f (1≤e≤f≤10000) ,分别表示存钱罐的初始重量和现在重量。 第二行输入一个整数 n (1≤n≤500),表示有 n 种硬币。 接下来有 n 行输入,每行两个整数 p,w (1≤p≤50000,1≤w≤10000),分别表示硬币的面额和硬币的重量。 ##### 输出 如果这些钱可以凑出存钱罐的重量,那么输出存钱罐里最少有多少钱;如果不能,输出impossible.。 #### 题解 这是一个特殊的多重背包问题,特殊在于必须装满背包(存钱罐)。 #### 代码 提示:不要忘记赋f[0]=0。 ```cpp #include <cstdio> #include <algorithm> using std::min; int n, g, p[500], w[500], f[10001]; int main(){ int tmp; scanf("%d%d%d", &tmp, &g, &n); g -= tmp; for(int i = 0; i < n; ++i){ scanf("%d%d", &p[i], &w[i]); } std::fill(f, f+g+1, 1e9); f[0] = 0; for(int i = 0; i < n; ++i){ for(int j = g; j >= w[i]; --j){ for(int k = 0; w[i]*k <= j; ++k){ f[j] = min(f[j], p[i]*k+f[j-w[i]*k]); } } } if(f[g] == 1e9) printf("impossible.\n"); else printf("%d\n", f[g]); return 0; } ``` ### 完全背包的时间/空间优化 ```cpp for(int i = 0; i < n; ++i) for(int j = 0; j <= m; ++j) f[j] = max(dp[j], f[j-v[i]]+w[i]); ``` ## 多重背包 多重背包问题和完全背包相似,但每件物品有数量限制。在选取每件物品件数时限制即可。 略。 ## 混合背包 即01背包,完全背包和多重背包的混合。参考多重背包解法。 略。 ## 分组背包 问题描述:有N组物品和一个容量为M的背包。第i组物品数量是$s_i$,其中第k个物品的体积是$v_{i,k}$, 价值是$w_{i,k}$,每组最多只能取一个物品。求选取这些物品放入背包,能够得到的最大价值。 ```cpp #include <cstdio> #include <algorithm> int v, n, t, c[11][31], w[11][31], s[11], f[250]; int main(){ scanf("%d%d%d", &v, &n, &t); for(int i = 0; i < n; ++i){ int in1, in2, group; scanf("%d%d%d", &in1, &in2, &group); c[group][++s[group]-1] = in1; w[group][s[group]-1] = in2; } for(int i = 1; i <= t; ++i){ for(int j = v; j >= 0; --j){ for(int k = 0; k < s[i]; ++k){ if(j >= c[i][k]) f[j] = std::max(f[j], f[j-c[i][k]]+w[i][k]); } } } printf("%d\n", f[v]); return 0; } ``` ## 二维费用背包 二维费用背包问题指:每件物品具有两种不同的费用,选择这件物品必须同时付出这两种代 价。每种代价有一个上限 (背包容量)。求选取物品可以得到的最大价值。 用一个题解演示求二维费用背包问题的一般化方法。 ### 题解 战利品 #### 题目 *题目有修改* ##### 描述 小信要把一些战利品放进袋子里。但他只有一个最多装下V体积物品的袋子,他不能全部放进去,而且他也拿不动那么重的东西。他估计自己能拿的最大重量为G。现在已知每个战利品的完美值、体积和重量。他想让袋子中装的战利品的完美值总和最大,接下来又得计划一下了。 ##### 输入 第一行:V 和 G 表示袋子能装下的最大体积和小信能拿的最大重量。 第二行:N 表示掉落的战利品数量。 第三到 N+2 行:每行 3 个数 $T_i, V_i, G_i$ 表示各战利品的完美值、体积和重量。 ##### 输出 输出共一个数,表示可能获得的最大完美值。 #### 题解 本题是一个二维费用的01背包,有体积V和重量G两种代价。在下面的代码中,f数组省略了表示物品序数的维度,详见上文01背包的空间优化。 #### 代码 ```cpp #include <cstdio> #include <algorithm> using std::max; int n, a[400], b[400], c[400], f[400][400]; int main(){ int v, g; scanf("%d%d%d", &v, &g, &n); for(int i = 0; i < n; ++i){ scanf("%d%d%d", &a[i], &b[i], &c[i]); } for(int i = 0; i < n; ++i){ for(int j = v; j >= b[i]; j--){ for(int k = g; k >= c[i]; --k){ f[j][k] = max(f[j][k], f[j-b[i]][k-c[i]]+a[i]); } } } printf("%d\n", f[v][g]); return 0; } ``` 话说既然有二维背包,应该有三维背包。可三维背包这种题,~~除了恶心人还要它何用?!~~ © 允许规范转载 赞赏 如果我的文章对你有用,请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
1 条评论