背包DP | 完全背包问题

小灰灰 2023-07-19 10:34 47阅读 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&plus;%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