3.Python算法之贪心算法思想

贪心算法

1.什么是贪心算法

2.贪心算法的特点和思路

3.贪心算法的缺点

4.贪心算法的基本思路

5.贪心算法的基本过程

6.贪心算法解决“找零”问题

6.贪心算法解决“汽车加油”问题

---

1.什么是贪心算法

      贪心算法也称为贪婪算法，它在求解问题时，总想用当前看来最好的方法来实现。这种算法思想不从整体最优上考虑问题，而仅仅考虑某种意义上的局部最优来求解问题。虽然贪心算法并不能得到所有问题的整体最优解，但是当面对范围相当广泛的许多问题时，能产生整体最优解或整体最优解的近似值。由此可见，贪心算法只是追求某个范围内最优，可以成为“温柔的贪婪”。

2.贪心算法的特点和思路

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

3.贪心算法的缺点

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

4.贪心算法的基本思路

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

5.贪心算法的基本过程

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

6.贪心算法解决“找零”问题

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

def main(): # 存储各种硬币的面值 coin_face_value = [0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0] # 存储每种硬币的数量 coin_num = [] # 拥有的零钱总和 coin_total_sum = 0 temp = input("请输入每种零钱的数量：") # 12 11 11 11 11 11 11 temp_list = temp.split(' ') for i in range(0, len(temp_list)): coin_num.append(int(temp_list[i])) # 用每种硬币的数量乘以面值，再累计求和 coin_total_sum += coin_num[i] * coin_face_value[i] give_change = float(input("请输入需要找的零钱：")) if give_change > coin_total_sum: # 当要找的零钱大于收银员的总金额时，无法找零 print("数据有错") return 0 # 收银员的硬币总数 - 找的零钱 # coin_total_sum = coin_total_sum - give_change # 要想用的硬币数量最少，需要利用所有大面值的硬币，因此从数组的大面值的元素开始遍历 i = len(coin_face_value) - 1 while i >= 0: if give_change >= coin_face_value[i]: # 需要的硬币个数 need_coin_number = int(give_change / coin_face_value[i]) if need_coin_number >= coin_num[i]: need_coin_number = coin_num[i] # 更新需要的硬币个数 # 零钱总和减去已经找掉的零钱 give_change -= need_coin_number * coin_face_value[i] print("用了%d个%.2f枚硬币" % (need_coin_number, coin_face_value[i])) i -= 1 if __name__ == '__main__': main()

执行后，首先输入拥有的硬币个数，然后输入需要找零的金额，例如 1.6，就会有找零的方案 

程序运行结果：

6.贪心算法解决“汽车加油”问题

    持续更新