贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来最好的选择。也就是说,不从整体最优上考虑,他所做出的是在某种意义上的局部最优解。

贪心算法不保证会得到全局最优解,但是在某些问题上的贪心算法的解,就是最优解。

找零问题

假设商店老板需要找零n元钱,钱的面额有100元、50元、20元、5元、1元,如何找零使得所需钱币的数量最少?

total = [100, 50, 20, 1]

def change(total, n):
    m = []
    for v in total:
        m.append({v: n // v})
        n %= v
    return m, n

print(change(total, 354))

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/339