小白学习动态规划：完全背包（经典例题）

青旅半醒 2021-08-26 18:23 331阅读 0赞

# 小白学习动态规划：完全背包 #

参考博客：

1.  https://blog.csdn.net/qq\_38984851/article/details/81133840
2.  https://blog.csdn.net/na\_beginning/article/details/62884939

--------------------

完全背包与零一背包类似，不同的是每种物品有无限件，意味着选完一件物品放进背包后，有可能会继续选择同一件物品放入背包。

## 经典例题 ##

有 N 种 物 品 和 一 个 容 量 为 V 的 背 包 ， 每 种 物 品 都 有 无 限 件 可 用 。 放 入 第 i 种 物 品 的 耗 费 的 空 间 是 C i ， 得 到 的 价 值 是 W i 。 求 解 ： 将 哪 些 物 品 装 入 背 包 ， 可 使 这 些 物 品 的 耗 费 的 空 间 总 和 不 超 过 背 包 容 量 ， 且 价 值 总 和 最 大 。 有N种物品和一个容量为V 的背包，每种物品都有无限件可用。 \\\\放入第i种物品的耗费的空间是C\_i，得到的价值是W\_i。\\\\求解：将哪些物品装入背包，可使 这些物品的耗费的空间总和不超过背包容量，且价值总和最大。 有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是Ci，得到的价值是Wi。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

例 ： N = 5 ， V = 10 例：N = 5，V=10 例：N=5，V=10

<table> 
 <thead> 
  <tr> 
   <th align="center">物品</th> 
   <th align="center">A</th> 
   <th align="center">B</th> 
   <th align="center">C</th> 
   <th align="center">D</th> 
   <th align="center">E</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">Wealth</td> 
   <td align="center">2</td> 
   <td align="center">4</td> 
   <td align="center">7</td> 
   <td align="center">8</td> 
   <td align="center">12</td> 
  </tr> 
  <tr> 
   <td align="center">Cost</td> 
   <td align="center">2</td> 
   <td align="center">3</td> 
   <td align="center">5</td> 
   <td align="center">6</td> 
   <td align="center">8</td> 
  </tr> 
 </tbody> 
</table>

## 初步解题思路 ##

定义状态与01背包相同，下标i代表前i件物品，下标j代表背包的总容量为j  
 此 问 题 与 01 背 包 问 题 类 似 ， 但 是 每 一 件 物 品 并 不 是 选 与 不 选 的 问 题 ， 而 是 选 几 件 的 问 题 ： 选 0 件 、 选 1 件 、 选 2 件 ⋅ ⋅ ⋅ 选 k 件 ( k ∗ C o s t \[ i \] ≤ V ) 此问题与01背包问题类似，但是每一件物品并不是选与不选的问题，\\\\而是选几件的问题：选0件、选1件、选2件···选k件(k\*Cost\[i\] ≤ V) 此问题与01背包问题类似，但是每一件物品并不是选与不选的问题，而是选几件的问题：选0件、选1件、选2件⋅⋅⋅选k件(k∗Cost\[i\]≤V)  
所以，在01背包的基础上改变一下

掌握完全背包问题前必须清楚**01背包的状态转移方程**：  
 d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] i f   C o s t \[ i \] > j d p \[ i − 1 \] \[ j − C o s t \[ i \] \] + W e a l t h \[ i \] i f   C o s t \[ i \] ≤ j dp\[i\]\[j\] = \\begin\{cases\} dp\[i-1\]\[j\]&if\\ Cost\[i\] > j\\\\ dp\[i-1\]\[j-Cost\[i\]\] + Wealth\[i\]&if\\ Cost\[i\] ≤j \\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j\]dp\[i−1\]\[j−Cost\[i\]\]\+Wealth\[i\]if Cost\[i\]>jif Cost\[i\]≤j  
而**完全背包的状态转移方程**为：  
 d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] i f   C o s t \[ i \] > j d p \[ i − 1 \] \[ j − k ∗ C o s t \[ i \] \] + k ∗ W e a l t h \[ i \] i f   k ∗ C o s t \[ i \] ≤ j dp\[i\]\[j\] = \\begin\{cases\} dp\[i-1\]\[j\]&if\\ Cost\[i\] > j\\\\ dp\[i-1\]\[j-k\*Cost\[i\]\] + k\*Wealth\[i\]&if\\ k\*Cost\[i\] ≤j \\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j\]dp\[i−1\]\[j−k∗Cost\[i\]\]\+k∗Wealth\[i\]if Cost\[i\]>jif k∗Cost\[i\]≤j

需要乘上系数k的原因是如果背包的容量大于物品A的体积，那么放入一件A之后，有可能背包剩下的容量还可以继续放入A物品，每次放入都要放入**尽可能多的**物品。

例如：

> 背包容量V = 9，物品A的体积为Cost\[A\] = 2，那么拿1件A放入背包后，背包容量 = 10 - 2 = 8，还可以继续放A，直到背包容量为剩下1时（此时放了4件A），无法继续放入A了才结束。

**代码实现：**

/** * @author Zeng * @date 2020/2/12 22:34 */
    public class Solution { 
    
        public static int maxWealth(int[] cost, int[] wealth, int N, int V){ 
            //给dp table加一行和一列避免复杂的初始化问题
            int[][] dp = new int[N+1][V+1];
            //初始化
            for (int i = 0; i < dp.length; i++){ 
                dp[i][0] = 0;
            }
            for (int i = 0; i < dp[0].length; i++){ 
                dp[0][i] = 0;
            }
            for (int i = 1; i < N+1; i++){ 
                for (int j = 1; j < V+1; j++){ 
                    //假设不选第i件
                    dp[i][j] = dp[i-1][j];
                    for (int k = 1; k*cost[i-1] <= j; k++){ 
                        //可以选k件
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - k*cost[i-1]] + k*wealth[i-1]);
                    }
                }
            }
            //观察dp table值
            for (int i = 0; i < N+1; i++){ 
                for (int j = 0; j < V+1; j++){ 
                    System.out.print(dp[i][j]+" ");
                }
                System.out.println();
            }
            return dp[N][V];
        }
    
        public static void main(String[] args) { 
            int[] cost = new int[]{ 2, 3, 4, 7};
            int[] wealth = new int[]{ 1, 3, 5, 9};
            int N = 4;
            int V = 10;
            int i = maxWealth(cost, wealth, N, V);
            System.out.println(i);
        }
    
    }

输出结果：
    0 0 0 0 0 0 0 0 0  0  0 
    0 0 2 2 4 4 6 6 8  8  10 
    0 0 2 4 4 6 8 8 10 12 12 
    0 0 2 4 4 7 8 9 11 12 14 
    0 0 2 4 4 7 8 9 11 12 14 
    0 0 2 4 4 7 8 9 12 12 14 
    14

此算法的空间复杂度为O（N²），共需要求解O（NV）个状态，求解每个状态的时间不是常数级了，因为每个物品并不是只有拿和不拿两种情况，而是拿k件（k≥1）或不拿的多种情况，求dp\[i\]\[j\]所需要的时间是O（j/Cost\[i\]）,所以总的时间复杂度为O（NVΣ(j/Cost\[i\])）。在这种复杂度较高的情况下一般是不能AC的。所以要优化时间复杂度。尝试将其转化为01背包问题。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]

## 优化解题思路（转化为01背包问题） ##

### 优化前的核心代码 ###

for (int i = 1; i < N+1; i++){ 
                for (int j = 1; j < V+1; j++){ 
                    //假设不选第i件
                    dp[i][j] = dp[i-1][j];
                    for (int k = 1; k*cost[i-1] <= j; k++){ 
                        //可以选k件
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - k*cost[i-1]] + k*wealth[i-1]);
                    }
                }
            }

### 思路1 ###

可以在每一个物品可以放多少个时，**直接求出可以放入的最大值k**，即每个物品要么不能放进去，要么放k件，等价于01背包中要么不能放入物品，要么可以放入1件物品。

**优化代码：**

for (int i = 1; i < N+1; i++){ 
        for (int j = 1; j < V+1; j++){ 
            //假设不选第i件
            dp[i][j] = dp[i-1][j];
            //假设能放k件
            int k = j / cost[i-1];
            //可以选k件
            dp[i][j] = Math.max(dp[i][j], dp[i-1][j - k*cost[i-1]] + k*wealth[i-1]);
        }
    }

### 思路2 ###

当物品可以放入时，可能还可以继续放入该物品，所以状态转移方程需要变化：  
 d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] i f   C o s t \[ i \] > j d p \[ i \] \[ j − C o s t \[ i \] \] + W e a l t h \[ i \] i f   C o s t \[ i \] ≤ j dp\[i\]\[j\] = \\begin\{cases\} dp\[i-1\]\[j\]&if\\ Cost\[i\] > j\\\\ dp\[i\]\[j-Cost\[i\]\] + Wealth\[i\]&if\\ Cost\[i\] ≤j \\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j\]dp\[i\]\[j−Cost\[i\]\]\+Wealth\[i\]if Cost\[i\]>jif Cost\[i\]≤j

当 C o s t \[ i \] ≤ j 时 ， 当 放 入 一 个 物 品 i 时 ， 之 后 还 可 能 会 放 入 物 品 i 所 以 状 态 转 移 方 程 是 F \[ i \] \[ j − C o s t \[ i \] \] + W e a l t h \[ i \] 而 不 是 F \[ i − 1 \] \[ j − C o s t \[ i \] \] + W e a l t h \[ i \] 。 当Cost\[i\] ≤ j时，当放入一个物品i时，之后还可能会放入物品i\\\\所以状态转移方程是F\[i\]\[j-Cost\[i\]\]+Wealth\[i\]而不是F\[i-1\]\[j-Cost\[i\]\]+Wealth\[i\]。 当Cost\[i\]≤j时，当放入一个物品i时，之后还可能会放入物品i所以状态转移方程是F\[i\]\[j−Cost\[i\]\]\+Wealth\[i\]而不是F\[i−1\]\[j−Cost\[i\]\]\+Wealth\[i\]。

**优化代码：**

for (int i = 1; i < N+1; i++){ 
        for (int j = 1; j < V+1; j++){ 
            //假设不选第i件
            dp[i][j] = dp[i-1][j];
            if(cost[i-1] < j){ 
                //可以放进去
                dp[i][j] = Math.max(dp[i][j], dp[i][j - k*cost[i-1]] + k*wealth[i-1]);
            }
        }
    }

### 思路3（二进制思想）（还没看懂） ###

--------------------

**时间有限，能力有限，如有错误欢迎指正！乐意与大家交流！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]: /images/20210511/cba1c1bd272d41bf9ed31a677c43783b.png