贪心算法之背包问题

上一博客我简单地介绍了用贪心算法来解决换钱问题，这一博客我简单地介绍一下背包问题。
1. 问题
2. 举例
3. 代码

1.问题

一个小偷在某个商店发现有n个商品，第i个商品价值$v_i$元，重$w_i$千克。 他希望拿走的价值尽量高，但他的背包最多只能容纳$W$千克的东西。他应该拿走哪些商品?

• 0-1背包: 对于一个商品，小偷要么把它完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次。 (比如商品为金条)
• 分数背包: 对于一个商品，小偷可以拿走其中任意一部分。(比如商品为金砂)

2.举例

举例:
商品1: V1=60 W=10
商品2: V2=100 W2=20
商品3: V3=120 W3=30
背包容量: W=50

注意：

1. 分数背包能用贪心算法来做，因为到最后肯定会把背包装满，所以我们每次只要把当前单位重量下，价值最高的放进背包知道背包满了就好

2. 0-1背包不能用贪心算法来解，因为可能会导致背包装不满，比如上面的例子，你先装了商品1发现只能再装一个商品2了，因为不能分割，就不能再装商品3了，所以就不行

解题思路:
解题思路其实可以有很多，我这里介绍一下最普遍的几种思路:
  1. 每次选取总价值V最高的商品，一直取，直到把该商品取完再剩下商品中价格最高的拿，直到背包全部装满。比如上面的例子，看起来商品3的价值最高，那就先拿商品3，把商品3拿完后，背包里就有W=30的商品了；接着拿商品2，拿完后发现背包搞好满了。那么现在，背包装满，背包里的商品价值为V=120+100=220。
  2. 每次取总重量最小的，这样我们就可以装尽可能多的商品了，一直取，直到该商品被取完，再取剩下商品中重量最小的拿。比如上面的例子，商品1的重量最小，就先取商品1，拿完后，背包里$V=60,W=10$；再取商品2，商品2取完后，背包里$V=160,W=30$；再取商品3，商品3取不完，只能取到背包满了为止，此时$V=160+80=240,W=50$.可以看出，第二种贪心思路的结果比第一种好。
  3. 每次取单位价值最高的商品，直到背包装满。 先算算各个商品的单位价值: $商品1=\frac{60}{10}=6，商品2=\frac{100}{20}=5，商品3=\frac{120}{30}=4$ 所以，先取商品1，把商品1取完后，再取商品2，商品2取完后，再取商品3，结果是和思路2一样的，最后背包里$V=60+100+80=240,W=50$

贪心算法并不是一种固定的算法，而是贪心思想+算法，而贪心思想的关键就在于每次取最优的，也不固定，所以贪心思想的应用场景就很广。

3.代码

这里我用了第三种思路，来编写代码:

'''
TOPIC: 用贪心算法解决分数背包的问题
author: Blue
time: 2020-08-18
QQ: 2458682080
'''

# 商品元组(价格，重量)
goods = [(60, 10), (100, 20), (120, 30)]
# 按照单位重量的价值进行降序排序
goods.sort(key=lambda x: x[0] / x[1], reverse=True)

def fractional_backpack(goods, w):
    # m表示每样商品拿多少
    m = [0 for _ in range(len(goods))]
    for i, (price, weight) in enumerate(goods):
        if w >= weight:
            m[i] = 1
            w -= weight
        else:
            m[i] = w / weight
            w = 0
            break
    return m

print(fractional_backpack(goods, 50))

结果为:

[1, 1, 0.6666666666666666]

结果和我们分析的一样，商品1、商品2全拿，商品3取$\frac{2}{3}$