小白学习动态规划：0-1背包（经典例题）

系统管理员 2021-05-12 11:49 478阅读 0赞

## 前言 ##

背包问题只是动态规划问题下的一个分类，求解0-1背包问题的思路本质上与求解动态规划的一般思路是一致的，我们经常遇到新的题目做不出来，并不是因为没有掌握动态规划的思想，而有可能是因为没有遇到这类具有显著特征的题目，无法将一般动态规划的解题思路应用在实战中。

动态规划的原理：

① **最优子结构性质**：问题的最优解可以转化为求子问题的最优解，也就是说问题的最优解可以从子问题的最优解中得出。

② **子问题重叠性质**：问题的解由子问题的解组成，所以先构造子问题的解，才能求出最终问题的解。而求问题的解时，由于已经记录子问题的解，所以不必重新求子问题的解，只需取出来使用即可。

## 经典例题 ##

有 N 件 物 品 和 一 个 容 量 为 V 的 背 包 。 放 入 第 i 件 物 品 耗 费 的 空 间 是 C i ， 得 到 的 价 值 是 W i 。 求 解 将 哪 些 物 品 装 入 背 包 可 使 价 值 总 和 最 大 。 有N件物品和一个容量为V 的背包。放入第i件物品耗费的空间是Ci，得到 的价值是Wi。 \\\\求解将哪些物品装入背包可使价值总和最大。 有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">3</td> 
   <td align="center">4</td> 
   <td align="center">5</td> 
   <td align="center">6</td> 
   <td align="center">7</td> 
  </tr> 
  <tr> 
   <td align="center">Cost</td> 
   <td align="center">1</td> 
   <td align="center">2</td> 
   <td align="center">5</td> 
   <td align="center">6</td> 
   <td align="center">8</td> 
  </tr> 
 </tbody> 
</table>

> 这是最基础的0-1背包问题

先看下图，是在求出问题的解后整个动态规划表呈现的结果。下面就来看看这张表是如何一步步填上去并求出最终问题解的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]

### 解题思路 ###

① 确定子问题

> 求容量为V的背包装入物品的价值总和最大，则考虑第i件物品是否放入背包，使得背包的价值保持最大。

② 确定状态及数组

> 用一个二维数组F\[i\]\[j\]表示前i件物品放入容量为j的背包中可以获得的最大价值（**注意此处的容量是背包的总容量，而不是背包的剩余容量**）

③ 确定边界值

> F\[0\]\[0…V\] = 0：表示不管第0件物品放入任意容量的背包中其最大价值都是0，因为不存在第0件物品。
> 
> F\[0…N\]\[0\] = 0：表示任意物品放入容量为0的背包中其最大价值都是0，因为容量为0的背包装不下任何物品。

④ 确定状态转移方程

> Ⅰ：若第i件物品**无法放入**容量为j的背包中  
>  则 前 i 件 物 品 放 入 容 量 为 j 的 背 包 中 的 最 大 价 值 等 于 前 i − 1 件 物 品 放 入 容 量 为 j 的 背 包 中 的 最 大 价 值 ， 即 ： F \[ i \] \[ j \] = F \[ i − 1 \] \[ j \] \\\\则前i件物品放入容量为j的背包中的最大价值等于前i-1件物品放入容量为j的背包中的最大价值，\\\\即：F\[i\]\[j\] = F\[i-1\]\[j\] 则前i件物品放入容量为j的背包中的最大价值等于前i−1件物品放入容量为j的背包中的最大价值，即：F\[i\]\[j\]=F\[i−1\]\[j\]  
> Ⅱ：若第i件物品**可以放入**容量为j的背包中，则分两种情况：  
>  第 i 件 物 品 放 入 容 量 为 j 的 背 包 中 ， 得 到 前 i 件 物 品 的 最 大 价 值 ： F 1 \[ i \] \[ j \] = F \[ i − 1 \] \[ j − C i \] + W i 第 i 件 物 品 不 放 入 容 量 为 j 的 背 包 中 ， 得 到 前 i 件 物 品 的 最 大 价 值 ： F 2 \[ i \] \[ j \] = F \[ i − 1 \] \[ j \] 取 F 1 还 是 F 2 取 决 于 谁 的 价 值 更 大 ， 即 ： F \[ i \] \[ j \] = m a x ( F 1 \[ i \] \[ j \] ,   F 2 \[ i \] \[ j \] ) 第i件物品放入容量为j的背包中，得到前i件物品的最大价值：F\_1\[i\]\[j\] = F\[i-1\]\[j-C\_i\] + W\_i \\\\第i件物品不放入容量为j的背包中，得到前i件物品的最大价值：F\_2\[i\]\[j\] = F\[i-1\]\[j\] \\\\取F\_1还是F\_2取决于谁的价值更大，即：F\[i\]\[j\] = max(F\_1\[i\]\[j\],\\ F\_2\[i\]\[j\]) 第i件物品放入容量为j的背包中，得到前i件物品的最大价值：F1\[i\]\[j\]=F\[i−1\]\[j−Ci\]\+Wi第i件物品不放入容量为j的背包中，得到前i件物品的最大价值：F2\[i\]\[j\]=F\[i−1\]\[j\]取F1还是F2取决于谁的价值更大，即：F\[i\]\[j\]=max(F1\[i\]\[j\], F2\[i\]\[j\])

例：

**第Ⅰ种情况：**  
![情况I][I]

当\[i，j\] = \[2，1\]时，物品B的耗费空间Cost=2，而背包的体积 j=1，很明显物品B无法放入背包中，所以  
 F \[ 2 \] \[ 1 \] = F \[ 1 \] \[ 1 \] = 3 F\[2\]\[1\] = F\[1\]\[1\] = 3 F\[2\]\[1\]=F\[1\]\[1\]=3  
**第Ⅱ种情况：**  
![情况II][II]  
当\[i，j\] = \[2，3\]时，物品B的耗费空间Cost = 2，而背包的体积 j=3，物品B可以放入背包中，所以  
 F \[ 2 \] \[ 3 \] = m a x ( F \[ 1 \] \[ 3 \] , F \[ 1 \] \[ 3 − 2 \] + 4 ) = m a x ( 3 , 3 + 4 ) = m a x ( 3 , 7 ) = 7 F\[2\]\[3\] = max(F\[1\]\[3\], F\[1\]\[3-2\] + 4)=max(3,3+4)=max(3,7)=7 F\[2\]\[3\]=max(F\[1\]\[3\],F\[1\]\[3−2\]\+4)=max(3,3\+4)=max(3,7)=7

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

作者在理解Ⅱ时有一个困惑：**为什么第i件物品可以放入容量为j的背包中还需要比较不放入的情况？**  
![图片2][2]  
 当 \[ i ， j \] = \[ 5 ， 9 \] 时 ， 物 品 E 需 要 占 用 C o s t = 8 ， 而 背 包 容 量 j = 9 > C o s t , 所 以 背 包 可 以 放 入 E 这 件 物 品 如 果 放 入 E ， 那 么 就 要 腾 出 E 的 空 间 ， 所 以 F 1 \[ 5 \] \[ 9 \] = F \[ 5 − 1 \] \[ 9 − C o s t E \] + W e a l t h E = 10 如 果 不 放 入 E ， 那 么 不 需 要 腾 出 E 的 空 间 ， 所 以 F E \[ 5 \] \[ 9 \] = F \[ 4 \] \[ 9 \] = 13 ， 可 以 看 到 不 放 入 E 反 而 让 背 包 的 总 价 值 更 大 当\[i，j\] = \[5，9\]时，物品E需要占用Cost=8，而背包容量j=9 > Cost,所以背包可以放入E这件物品\\\\ 如果放入E，那么就要腾出E的空间，所以F\_1\[5\]\[9\] = F\[5-1\]\[9-Cost\_E\] + Wealth\_E = 10\\\\ 如果不放入E，那么不需要腾出E的空间，所以F\_E\[5\]\[9\] = F\[4\]\[9\]=13，可以看到不放入E反而让背包的总价值更大\\\\ 当\[i，j\]=\[5，9\]时，物品E需要占用Cost=8，而背包容量j=9>Cost,所以背包可以放入E这件物品如果放入E，那么就要腾出E的空间，所以F1\[5\]\[9\]=F\[5−1\]\[9−CostE\]\+WealthE=10如果不放入E，那么不需要腾出E的空间，所以FE\[5\]\[9\]=F\[4\]\[9\]=13，可以看到不放入E反而让背包的总价值更大  
**所以并不是说物品E可以放入就马上放入，因为每放入一件物品都要腾出相应的空间**  
 V 腾 出 的 空 间 = C o s t i V\_\{腾出的空间\} = Cost\_i V腾出的空间=Costi  
而腾出的空间可以放入其它物品，而**有可能放入其它的物品价值总和大于物品E的价值**。

⑤ 代码实现

public class Solution{ 
        public int dp(int[] wealth, int[] cost, int V, int N){ 
            //特殊状态处理
            if(wealth.length != cost.length){ return -1;}
            if(wealth.length == 0){ return 0;}
            if(wealth.length == 1){ 
                if(cost[0] > V){ 
                    return 0;
                }else{ 
                    return wealth[0];
                }
            }
            int[][] F = new int[N + 1][V+1];
            //边界值处理
            for(int i = 1; i < N + 1; i++){ 
                for(int j = 1; j < V + 1; j++){ 
                    //先假设不能放入容量为j的背包
                    F[i][j] = F[i-1][j];
                    //判断能不能放入背包
                    if(j >= cost[i-1]){ 
                        F[i][j] = Math.max(F[i-1][j], F[i-1][j-cost[i-1]] + wealth[i-1]);
                    }
                }
            }
            return F[N][V];
        }
    }

**时间有限，能力有限，若有误希望能够指出，乐意与大家交流！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]: /images/20210511/f72f0fd5acc44cae98dc79346a299025.png
[I]: /images/20210511/6bfa8a1bf3ce4659a4a17e68d20427a4.png
[II]: /images/20210511/34a6f7e2a1374230867d8ce67335d503.png
[2]: /images/20210511/8339d8a5df2a47e583b6686dd10bda1b.png