贪心算法思想

贪心算法从问题的某个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。

存在的问题

不能保证最后的解是最优的。
不能用来求最大解或最小解问题。
只能求满足某些约束条件的可行解范围。

基本思路

建立数学模型来描述问题。
把求解的问题分成若干个子问题。
对每一个子问题求解，得到子问题的局部最优解。
把子问题的局部最优解合并成原来问题的一个解。

基本过程

从问题的某一初始解出发。
while 能向给定总目标前进一步。
求出可行解的一个解元素。
由所有解元素组合成问题的一个可行解。

“找零”问题

问题描述：假设只有 1 分、2 分、5 分、1 角、2 角、5 角、1 元面值的硬币。在超市结账时，如果需要找零钱，收银员希望将最少的硬币数找给顾客。那么，给定需要找的零钱数目，如何求得最少的硬币数？

def main():
    d = [0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0]  # 存储每种硬币的面值
    d_num = []  # 存储每种硬币的数量
    s = 0  # 拥有的零钱总和

    temp = input('请输入每种零钱的数量：')
    d_num0 = temp.split(' ')

    for i in range(0, len(d_num0)):
        d_num.append(int(d_num0[i]))
        s += d[i] * d_num[i]

    sum = float(input('请输入需要找的零钱：'))

    assert s >= sum

    # 从数组中最大面值的元素开始遍历
    i = len(d) - 1
    while i >= 0:
        if sum >= d[i]:
            n = int(sum / d[i])
            if n >= d_num[i]:
                n = d_num[i]
            sum -= n * d[i]
            print('用了%d个%f枚硬币'%(n, d[i]))
        i -= 1

if __name__ == '__main__':
    main()

请输入每种零钱的数量：5 5 5 3 2 2 1
请输入需要找的零钱：1.6
用了1个1.000000枚硬币
用了1个0.500000枚硬币
用了1个0.100000枚硬币

“汽车加油”问题

问题描述：一辆汽车加满油后可行驶 n 千米，旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的 n(n<=5000) 千米和 k(k<=1000) 个加油站位置，编程计算最少加油次数。

def greedy(n ,k, d):
    num = 0  # 加油次数
    for i in range(k):
        if d[i] > n:
            print('no solution')
            return

    i, s = 0, 0
    while i <= k:
        s += d[i]
        if s >= n:
            s = d[i]
            num += 1
        i += 1

    print(num)

if __name__ == '__main__':
    n = 100  # 加满油可行驶的距离
    k = 5  # 加油站数量
    d = [50, 80, 39, 60, 40, 32]  # 加油站之间的距离
    greedy(n, k, d)  # 3