设计思想之贪心

什么是贪心

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

应用贪心的示例

硬币找零问题

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)
0%