第三天：《LeetCode一天一例》-----0-1背包问题（python实现）

ゞ浴缸里的玫瑰 2022-03-09 06:26 403阅读 0赞

# 0-1背包问题 #

>          题目： 给定物品的重量weights=\[1, 2, 5, 6, 7\] ，对应的价值values=\[1, 6, 18, 22, 28\] ， 背包能装的最大重量为capicity=11。问：我们用这个背包装什么物品能获得最大价值？  注意：每件物品只有一件。并且最终重量不能超过背包所能承载的重量。

###   分析： ###

首先，说明一下，本题采用动态规划， 因为问题的本身含最优子结构。 我们先给出转态转移方程：

![20190312163043230.png][]

c(i, w)  表示包容量为w时，考虑前i个物品所能获得的最大价值。。 i表示第i个物品，w表示包容量

第一种情况： 当前物品的重量超过了包的承载量，显然装不上，那它当前的最大价值就是原有包中的价值（不装这个物品时的最大价值）。

第二种情况：当前物品的重量没有包承载量大。则说明当前这个物品可以装进去。 那我们就得考虑了： 装这个物品价值大还是不装这个物品价值大？  从两种情况中选最大的。

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td colspan="2">capicity</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
   <td>8</td> 
   <td>9</td> 
   <td>10</td> 
   <td>11</td> 
  </tr> 
  <tr> 
   <td>weight</td> 
   <td>value</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>6</td> 
   <td>0</td> 
   <td>1</td> 
   <td>6</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>18</td> 
   <td>0</td> 
   <td>1</td> 
   <td>6</td> 
   <td>7</td> 
   <td>7</td> 
   <td>18</td> 
   <td>19</td> 
   <td>24</td> 
   <td>25</td> 
   <td>25</td> 
   <td>25</td> 
   <td>25</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>22</td> 
   <td>0</td> 
   <td>1</td> 
   <td>6</td> 
   <td>7</td> 
   <td>7</td> 
   <td>18</td> 
   <td>22</td> 
   <td>24</td> 
   <td>28</td> 
   <td>29</td> 
   <td>29</td> 
   <td>40</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>28</td> 
   <td>0</td> 
   <td>1</td> 
   <td>6</td> 
   <td>7</td> 
   <td>7</td> 
   <td>18</td> 
   <td>22</td> 
   <td>28</td> 
   <td>29</td> 
   <td>34</td> 
   <td>35</td> 
   <td>40</td> 
  </tr> 
 </tbody> 
</table>

上述就是本题手工计算得出的矩阵。  右下角的40, 就是我们所能获得的最大价值

接着，我们还需要输出获得最大价值的时候，我们拿了什么物品

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70][]

从右下角的40开始， 背包容量为11，由于40 与上一行的40相等， 说明我们没有装第五个物品（因为当背包容量为11，装第四个物品的时候，价值已经到达了40）。 紧接着， 在背包容量为11时，对应第三个物品，最大价值是25， 所以，我们装了第四个物品。  此时，我们的背包容量变为W-w4  即：11-6=5。  所以，对于第三个物品，我们直接考虑在背包容量为5的时候， 可以看出价值是18，考虑有没有装第三个？ 因为背包容量为5时，第二个物品所对应的最大价值为7. 所以我们装了第三个物品。  接在：W剩 - w3 = 5-5 = 0 。  我们就可以得出背包中装了第三个和第四个物品。

### 代码实现： ###

#  01 背包问题
    def bag_01(weights, values, capicity):
    
        # [*, *, *, *, *, *, *, *, *, *, *, *]
        # [*, *, *, *, *, *, *, *, *, *, *, *]
        # [*, *, *, *, *, *, *, *, *, *, *, *]
        # [*, *, *, *, *, *, *, *, *, *, *, *]
        # [*, *, *, *, *, *, *, *, *, *, *, *]
        # [*, *, *, *, *, *, *, *, *, *, *, *]
        n = len(values)
        f = [[0 for j in range(capicity+1)] for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, capicity+1):
                f[i][j] = f[i-1][j]
                if j >= weights[i-1] and f[i][j] < f[i-1][j-weights[i-1]] + values[i-1]:
                    f[i][j] = f[i-1][j-weights[i-1]] + values[i-1]
        return f
    
    def show(capicity, weights, f):
        n = len(weights)
        print("最大价值:", f[n][capicity])
        x = [False for i in range(n)]
        j = capicity
        for i in range(n, 0, -1):
            if f[i][j] > f[i-1][j]:
                x[i-1] = True
                j -= weights[i-1]
        print("背包中所装物品为:")
        for i in range(n):
            if x[i]:
                print("第{}个".format(i+1))
    
    
    if __name__ == '__main__':
        # weights 指的是物品的重量
        # values 指的是物品的价值
        # capicity 指的是袋子能装的重量
        n = 5
        weights = [1, 2, 5, 6, 7]
        values = [1, 6, 18, 22, 28]
        capicity = 11
        m = bag_01(weights, values, capicity)
        # 打印矩阵
        for i in range(len(m)):
            print(m[i])
    
        # 接下来输出要装的物品
        show(capicity, weights, m)

### 输出结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1][]

[20190312163043230.png]: /images/20220309/da3c468f909c40efbc1f261ea7a26456.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220309/67cd9c13386a4c27b0494331fcaa498f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1]: /images/20220309/82872e58d692440086a996d5e9484166.png