背包DP | 完全背包问题 小灰灰 2023-07-19 10:34 1阅读 0赞 > **完全背包问题：**有**n种**物品，每一件的物品重量为 w\[ i \]，价值为 c\[ i \]。现有一个容量为V的背包 (背包的最大承重为V)，问如何选取物品放入背包，使得背包内物品的总价值最大，最大为多少？**（每一种物品均有无穷件）** -------------------- **完全背包与01背包的区别 ** 完全背包与 [背包DP | 01背包问题][DP _ 01] 的唯一区别就在于：01背包问题每一种物品只有一件，你只能选择0件或1件。而完全背包问题每一种物品有无穷件，对于同一种物品你可以同时选取1件、2件...只要不超过容量V即可。 -------------------- ### 1、算法分析 ### 令**dp\[ i \] \[ j \]** 表示在前 i 种物品中选取部分物品，能放入背包容量为 j （**可以不装满**）的最大价值（最优解）。其中![gif.latex_1_5Cleq_20i_5Cleq_20n_2C0_5Cleq_20j_5Cleq_20V][]。那么如何求解最优解呢？下面考虑对第 i 种物品的选择策略： 情况1：j < w\[ i \] * 不可能放入放第 i 种物品：那么问题就转化为前 i - 1 件物品恰好装入背包容量为 j 的最优解 情况2： j >= w\[ i \] * 不放第 i 种物品：那么问题就转化为 前 i - 1种物品恰好装入背包容量为 j 的最优解 * 放第 i 种物品：那么问题就转化为为 前 i 种物品恰好装入背包容量为 j - w\[ i \] 的最优解 + c\[ i \] （注意：这里选择放入第 i 种物品的选择之前，可能也是放入了第 i 种物品的！） **状态转移方程如下：** 当 i = 0 或 j = 0（边界条件） ：![dp\[i\]\[j\] = 0][dp_i_j_ _ 0] 当 ![1\\leq i\\leq n][1_leq i_leq n] * ![w\[i\]\\leq j\\leq V][w_i_leq j_leq V]：![dp\[i\]\[j\] = max (dp\[i-1\]\[j\], dp\[i\]\[j-w\[i\]\] + c\[i\])][dp_i_j_ _ max _dp_i-1_j_ dp_i_j-w_i_ _ c_i] * ![1 \\leq j < w\[i\]][1 _leq j _ w_i]：![dp\[i\]\[j\] = dp\[i-1\]\[j\]][dp_i_j_ _ dp_i-1_j] 最终答案就储存在 dp\[n\]\[V\] 中 -------------------- ### 2、过程示例 ### 对于n = 5， V = 10 的情况 : ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][] -------------------- ### 3、代码实现 ### #include <algorithm> #include <cstdio> using namespace std; #define MAXN 100 #define MAXV 100 /* 完全背包问题：有n种物品，每一件的物品重量为 w[ i ]，价值为 c[ i ]。 * 现有一个容量为V的背包 (背包的最大承重为V)，问如何选取物品放入背包， * 使得背包内物品的总价值最大，最大为多少？（每一种物品均有无穷件） */ int fun(int n, int v, int w[], int c[]) { int dp[MAXN][MAXV] = {0}; for (int i = 1; i <= n; i++) //i为当前可选物品 for (int j = 1; j <= v; j++) { //j为最大容量 if (w[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]); } return dp[n][v]; } -------------------- -------------------- **有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ ** -------------------- # end # 欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。 *---- 做最乖巧的博客er，做最扎实的程序员 ----* 旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~ ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1] [DP _ 01]: https://blog.csdn.net/weixin_43787043/article/details/105189350 [gif.latex_1_5Cleq_20i_5Cleq_20n_2C0_5Cleq_20j_5Cleq_20V]: https://private.codecogs.com/gif.latex?1%5Cleq%20i%5Cleq%20n%2C0%5Cleq%20j%5Cleq%20V [dp_i_j_ _ 0]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%5Bj%5D%20%3D%200 [1_leq i_leq n]: https://private.codecogs.com/gif.latex?1%5Cleq%20i%5Cleq%20n [w_i_leq j_leq V]: https://private.codecogs.com/gif.latex?w%5Bi%5D%5Cleq%20j%5Cleq%20V [dp_i_j_ _ max _dp_i-1_j_ dp_i_j-w_i_ _ c_i]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%5Bj%5D%20%3D%20max%20%28dp%5Bi-1%5D%5Bj%5D%2C%20dp%5Bi-1%5D%5Bj-w%5Bi%5D%5D%20+%20c%5Bi%5D%29 [1 _leq j _ w_i]: https://private.codecogs.com/gif.latex?1%20%5Cleq%20j%20%3C%20w%5Bi%5D [dp_i_j_ _ dp_i-1_j]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%5Bj%5D%20%3D%20dp%5Bi-1%5D%5Bj%5D [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/823cb373af3f47a794eb4b8672e6e0e6.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/b259eec371634781aa65881fa4c75bec.png
还没有评论，来说两句吧...