26 贪心算法

贪婪虽然不是一种好行为，但确是一种不错的算法

大纲

• 营养搭配问题

• 贪心算法求解

• 换硬币问题

营养搭配问题

根据前面学到的集合知识，下面我们想解决一个营养搭配的问题，假设我们有几种蔬菜水果可以选择，每种果蔬各自包含不同的营养成份，如果我们需要一个营养组成，如何选择最少的果蔬，使得这些营养都得到。

假设我们一共需要8种营养成份，这些信息我们存放在一个叫做nutrients的集合中。

nutrients = set(['a','b','c','d','e','f','g','h'])

然后用一个字典来存放7种果蔬和对应的营养成份。问题就是如何来选择最少的果蔬组合，使其营养成份达到标准。

foods = dict()
foods['香蕉'] = set(['a','c'])
foods['苹果'] = set(['b','c'])
foods['李子'] = set(['a','c','h'])
foods['西瓜'] = set(['d','e'])
foods['白菜'] = set(['f','h'])
foods['胡萝卜'] = set(['d','g'])
foods['西红柿'] = set(['c','d','e'])

foods

{'香蕉': {'a', 'c'},
 '苹果': {'b', 'c'},
 '李子': {'a', 'c', 'h'},
 '西瓜': {'d', 'e'},
 '白菜': {'f', 'h'},
 '胡萝卜': {'d', 'g'},
 '西红柿': {'c', 'd', 'e'}}

一种自然的思路是使用暴力求解的方法，也就是我们穷举出所有可能的果蔬组合，对每一种组合来看营养成份是否达到。那我们就加载导入之前学到的combinations函数。

from itertools import combinations

下面是所有2元素构成的组合。

list(combinations(foods.keys(),2))

[('香蕉', '苹果'),
 ('香蕉', '李子'),
 ('香蕉', '西瓜'),
 ('香蕉', '白菜'),
 ('香蕉', '胡萝卜'),
 ('香蕉', '西红柿'),
 ('苹果', '李子'),
 ('苹果', '西瓜'),
 ('苹果', '白菜'),
 ('苹果', '胡萝卜'),
 ('苹果', '西红柿'),
 ('李子', '西瓜'),
 ('李子', '白菜'),
 ('李子', '胡萝卜'),
 ('李子', '西红柿'),
 ('西瓜', '白菜'),
 ('西瓜', '胡萝卜'),
 ('西瓜', '西红柿'),
 ('白菜', '胡萝卜'),
 ('白菜', '西红柿'),
 ('胡萝卜', '西红柿')]

因为不清楚一个组合中2个元素的食物是否够，所以会去遍历所有k个元素的食物组合，这个k从2到7。下面来定义一个穷举的函数。

def brute_force(foods,nutrients,k):
    output_list = list()
    nutrients_selec = set()
    for food_list in combinations(foods.keys(),k):
        nutrients_selec = set()
        for food in food_list:
            nutrients_selec.update(foods[food])
        if nutrients <= nutrients_selec:
            output_list.append(food_list)
    return output_list

在上面的函数中，我们定义了一个双重循环，外层循环是对所有的果蔬组合进行遍历，内层循环是对某个组合中的所有元素进行遍历。将果蔬组合的营养成分进行合并，如果需要的营养成份是组合的营养成份的子集，我们就返回这个果蔬组合。函数的输入是可选择的果蔬食物，需要的营养，和组合参数k。

for i in range(len(foods)):
    output = brute_force(foods,nutrients,i)
    if len(output)>0:
        print(i)
        print(output)

5
[('香蕉', '苹果', '西瓜', '白菜', '胡萝卜'), ('香蕉', '苹果', '白菜', '胡萝卜', '西红柿'), ('苹果', '李子', '西瓜', '白菜', '胡萝卜'), ('苹果', '李子', '白菜', '胡萝卜', '西红柿')]
6
[('香蕉', '苹果', '李子', '西瓜', '白菜', '胡萝卜'), ('香蕉', '苹果', '李子', '白菜', '胡萝卜', '西红柿'), ('香蕉', '苹果', '西瓜', '白菜', '胡萝卜', '西红柿'), ('苹果', '李子', '西瓜', '白菜', '胡萝卜', '西红柿')]

然后我们用一个循环来显示出所有可能的组合参数，我们发现在5种以下的果蔬组合是不可能达到营养标准的，所以最少是5种食物的组合，发现其中有4个组合是营养达标的。

贪心算法求解

另一种巧妙的思路是使用贪婪方法，又称为贪心算法。其基本思想是，只看当前这一步，如何能使这当前一步的操作，最大化的满足需求。回到果蔬组合的例子中，我们先遍历所有的果蔬，看哪一种果蔬可以覆盖最多的营养，然后再看剩下的果蔬中，哪一种可以覆盖剩下未覆盖的营养成份。以此类推。

def greedy_func(foods, nutrients):
    final_food = set()
    while nutrients:
        best_food = None
        nutrient_covered = set()
        for food,nutrient in foods.items(): # 遍历所有的果蔬，求出营养覆盖最多
            covered = nutrients & nutrient  # 求交集
            if len(covered) > len(nutrient_covered):
                best_food = food
                nutrient_covered = covered
        nutrients = nutrients - nutrient_covered # 将覆盖的营养成份从原来的集合中去除
        final_food.add(best_food)  # 将对应的食物加入空集
    return final_food

greedy_func(foods,nutrients)

{'李子', '白菜', '胡萝卜', '苹果', '西瓜'}

小结：从这个例子可以对比贪心算法的答案和穷举的答案，可以看到贪心算法只提供了一种解答，而穷举得到了所有四种解答。不过，贪心算法的速度会比穷举快很多。

换硬币问题

贪心算法另一种经典应用是换硬币问题，如果我们手上有一定金额的钱，需要换成硬币，如何使用最少的硬币来换。

coins = [1,2,5,10,20,50,100]     #1分，2分，5分，1角，2角，5角，1元
coin_cnt = [10,10,10,10,10,10,10] # 存储每种硬币的数量
money = 13.2  # 需要换的总额
money = money*100

先用列表来定义可用的硬币面值和硬币数量，再定义需要换钱的金额是13.2元。

用一个字典来保存换硬币的面值和量，存在change里。基于贪心算法，也从面值最大的硬币换起，看最大面值的硬币能换多少个。如果需要硬币数量超过能提供的硬币个数，则将n变为能提供的硬币个数。最后一步是关键，需要将原来的金额money进行修改，改成前面换硬币后剩下的金额，使用减法进行了更新。

change = {}
# 要想用的钱币数量最少，那么需要利用所有面值大的钱币，因此从数组的面值大的元素开始遍历
i = len(coins)-1
while i >= 0: 
    if money >= coins[i]:
        n = int(money / coins[i]) # 需要硬币个数
        if n >= coin_cnt[i]: # 需要硬币数量超过能提供的硬币个数
            n = coin_cnt[i]  # 更新n
        change[coins[i]] = n # 用字典更新
        money = money - n * coins[i] # 令总金额动态的改变，
        print("使用了{x}面额硬币{y}个".format(x=int(coins[i]), y=n))
    i = i-1
print(change)

使用了100面额硬币10个
使用了50面额硬币6个
使用了20面额硬币1个
{100: 10, 50: 6, 20: 1}