• 概述
• 实现该算法的过程
• 活动选择问题
• 问题描述
• 代码
• 输出
• 人民币找零问题
• 问题描述
• 代码
• 输出

概述

贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

实现该算法的过程

1. 从问题的某一初始解出发；

2. while 能朝给定总目标前进一步

1. do，求出可行解的一个解元素；

3. 最后，由所有解元素组合成问题的一个可行解。

活动选择问题

问题描述

假设我们存在这样一个活动集合S={a1,a2,a3,a4,...,an}S={a1,a2,a3,a4,...,an},其中每一个活动aiai都有一个开始时间si和结束时间fi保证(0≤si<fi)fi保证(0≤si<fi),活动a_i进行时，那么它占用的时间为[si,fi).现在这些活动占用一个共同的资源，就是这些活动会在某一时间段里面进行安排，如果两个活动ai和aj的占用时间[si,fi),[sj,fj)不重叠，那么就说明这两个活动是兼容的，也就是说当si<=fj或者sj<=fi,那么活动ai,aj是兼容的。 
比如下面的活动集合S: 
我们假定在这个活动集合里面，都是按照fi进行升序排序的 

绿色是我们选择出来的最优解，也就是在满足“不重叠”的条件下“结束时间最早”的活动。

代码

#! /usr/bin/python
# -*- coding:utf-8 -*-
s = [-1,1,3,0,5,3,5,6,8,8,2,12];
f = [-1,4,5,6,7,8,9,10,11,12,13,14];
num = 0 # 起始条件
def greedyActivitySelector(start_index):
    global num
    for j in range(start_index + 1, len(f)):
        # 由于活动已经按结束时间排序，因此我们只需要考虑开始时间就可以了
        if (s[j] >= f[num]): # 如果开始时间晚于上一个结束的活动
            print "当前[%d, %d)最优选择：活动%d[%d, %d)" % (s[num], f[num], j, s[j], f[j])
            num = j
    return start_index
if __name__ == "__main__":
    for index in range(num, len(s)):
        greedyActivitySelector(index)

输出

人民币找零问题

问题描述

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？

用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。我们假设已经事先将面值按照从小到大的顺序排好。

代码

#! /usr/bin/python
# -*- coding:utf-8 -*-
values = [1, 2, 5, 10, 20, 50, 100];
counts = [3, 1, 2, 1, 1, 3, 5];
def moneyChange(money):
    result = [0] * len(values)
    for i in range(len(values) - 1, -1, -1):
        # 需要最大面额人民币张数
        c = min(money / values[i], counts[i])
        # 剩下钱数
        money = money - c * values[i]
        result[i] = c
    return result
if __name__ == "__main__":
    result = moneyChange(442)
    total = 0
    for i in range(len(result)):
        total += values[i] * result[i]
        print "需要面额(%d)元的人民币(%d)张" % (values[i], result[i])
    print "总额：%d元" % total

输出

0≤f1≤f2≤f3≤...≤fn