设计思想之贪心

发表于 更新于
贪心法又称贪婪法，是指在对问题求解时总是做出在当前看来是最好的选择。

什么是贪心

所谓贪心法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

应用贪心的示例

硬币找零问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def MinCoinCount(total, values):
    rest = total   # 可用余额
    count = 0
    # 从大到小遍历所有面值
    for i in range(len(values)):
        currentCount = rest // values[i] # 计算当前面值最多能用多少个
        rest -= currentCount * values[i]
        count += currentCount # 增加当前面额用量
        if (rest == 0):
            print(count)
            return count

if __name__ == '__main__':
    values = [5, 2, 1]   # 从大到小排列
    total = 22
    MinCoinCount(total, values)