貪心算法的思想：
貪心算法是指：在每一步求解的步驟中握截，它要求“貪婪”的選擇最佳操作卸奉，并希望通過一系列的最優(yōu)選擇睬塌，能夠產(chǎn)生一個(gè)問題的（全局的）最優(yōu)解堤器。
貪心算法每一步必須滿足一下條件：
1昆庇、可行的：即它必須滿足問題的約束。
2吼旧、局部最優(yōu)：他是當(dāng)前步驟中所有可行選擇中最佳的局部選擇凰锡。
3、不可取消：即選擇一旦做出，在算法的后面步驟就不可改變了掂为。
貪心算法的經(jīng)典例子：
? ? ? ?活動選擇問題裕膀，找零錢問題，搖擺問題勇哗，刪數(shù)問題等昼扛。
以找零問題為例來闡述貪心算法的具體步驟：
問題描述：假設(shè)商店老板需要找零n元錢，錢幣的面額有：100元欲诺、50元抄谐、20元、10元扰法，5元蛹含、1元，如何找零使得所需錢幣的數(shù)量最腥洹浦箱？
解題思路：貪心選擇：老板要找零99元的話，他有上面的面值分別為50祠锣，20酷窥，10，5伴网，1元的鈔票蓬推，為了找給我最少的硬幣數(shù)，他首先考慮50元的澡腾，能找99/50=1張沸伏，然后看20元，能找49/20=2張蛋铆，剩下9元馋评，然后看10元，不能找刺啦，那么就考慮5元… 即每次考慮當(dāng)前看起來最優(yōu)的選擇。
最優(yōu)子結(jié)構(gòu)：從初始狀態(tài)出發(fā)纠脾，每步都經(jīng)過貪心選擇玛瘸，最終得到問題的最優(yōu)解。第一張50元是第一步找零局部最優(yōu)苟蹈，以此每步達(dá)到局部最優(yōu)糊渊。寄希望于局部最優(yōu)的選擇能夠?qū)е氯肿顑?yōu)解。
代碼實(shí)現(xiàn)：
# -*- coding: utf-8 -*-
"""
Created on Sat Mar? 6 14:37:15 2021
@author: iron
"""
#貪心算法例子
t = [100, 50, 20, 10, 5, 1]
def change(t, n):? # n指的總金額
? ? m = [0 for _ in range(len(t))]? # 創(chuàng)建一個(gè)和t一樣長但全是0的列表
? ? # 這里假設(shè)t都是倒序排好的
? ? for i, money in enumerate(t):
? ? ? ? m[i] = n // money? # n整除money:376//100=3
? ? ? ? n = n % money? # n對money取余:376%100=76
? ? return m, n? # 如果到最后找不開慧脱，n就是找不開的錢
print(change(t, 376))? # ([3, 1, 1, 1, 1], 0)? 即：300+50+20+5+1
# 如果t = [100, 50, 20, 5]渺绒，則有1塊錢找不開，
print(change(t, 451))? # ([4, 1, 0, 0], 1)
結(jié)果展示：
當(dāng)找零376元時(shí)：需要3張100元，1張50元宗兼，一張20元躏鱼，一張5元，一張1元殷绍。
當(dāng)找零451元時(shí)：需要4張100元染苛，1張50元，一張1元主到。
