我們前面其實已經用了不少貪婪演算法(e.g. Prim’s, Kruskal algorithm, Dijkstra’s algorithm......)，從前面的例子裡你會發現到貪婪演算法是一種在求解問題時，每一步都選擇當前步驟的最佳解(最優選擇，而不考慮後面的結果。(期待每一個局部最佳解最後會變成全域最佳解，但其實未必會是全域最佳解)其通常用於優化問題時，在一系列選擇中做出一系列決策，以達到整體最優解。那典型在貪婪演算法會出現的例子包含，活動選擇問題(activity selection problem)、換錢問題(coin change problem)和分數背包問題(fractional knapsack problem)。見以下說明:

活動選擇問題 (activity selection problem)

假設現在有N個活動，每個活動有它的起始和結束時間。我們今天需要在有限的時間裡，選擇最多的活動，且一次只能參加一個活動。

# 這裡我們有一系列的活動，分別給上['活動名稱','開始時間','結束時間']
activities=[['A1',0,6],
            ['A2',3,4],
            ['A3',1,2],
            ['A4',5,8],
            ['A5',5,7],
            ['A6',8,9]]
# 我們先按結束時間由小到大排序，然後若下一個活動的開始時間比上一個活動晚的話，直接把它加入選擇
def GreedyForActivity(activities):
    activities=sorted(activities,key=lambda x:x[2])
    selectA=[]
    for event in activities:
        if selectA==[]:
            selectA.append(event)
        elif event[1]>selectA[-1][2]:
            selectA.append(event)
    return selectA

print(GreedyForActivity(activities))
>> [['A3', 1, 2], ['A2', 3, 4], ['A5', 5, 7], ['A6', 8, 9]]
# 我們最後得到參加活動A3,A2,A5和A6

換錢問題 (coin change problem)

今天有不同面值(1,2,5,10,20,50,100,1000)的硬幣(無限供應)還有你需要給的錢的面額($302)，找出最少硬幣的組合但能達到你給的面額。

#這裡我們input總共的面額，還有可以用的面額(list)
def coinchange(amount,clist):
    clist.sort()
    index=len(clist)-1
    cnum=dict.fromkeys(clist,0)
    while True:
        if amount-clist[index]>0:
            amount=amount-clist[index]
            cnum[clist[index]]+=1

        elif amount-clist[index]<0:
            index-=1
        else:
            cnum[clist[index]]+=1
            break
    res='面額:數量\n'
    for key,value in cnum.items():
        if value!=0:
            res+=f'{key} : {value}\n'
    return res
coins=[1,2,5,20,50,100]
print(coinchange(301,coins))
>>
    面額:數量
    1 : 1
    100 : 3

分數背包問題 (fractional knapsack problem)

假設你有一組物品，每個物品有重量和價值，你要決定每個物品要放多少(一個物品可以只放一部份，每個物品只有一份)在一個重量有限的箱子裡，使箱子內的物品總價值最高。

# 為了後面方便比較，這裡再寫個__lt__讓item可以直接用density來比較
class Item:
    def __init__(self,weight,value):
        self.weight=weight
        self.value=value
        self.density=value/weight
    def __lt__(self,other):
        return self.density<other.density
        
# 我們先將物品依密度由大到小排序，再依序放入箱子，最後放不下的時候，把最後一個物件拆惹
def FindMaxCom(products,maxCap):
    products.sort(reverse=True)
    unused=maxCap
    total_value=0
    res=[]
    for i in products:
        if unused-i.weight>=0:
            total_value+=i.value 
            unused-=i.weight
            res.append([i.weight,i.value,1])
        elif unused-i.weight<0:
            ratio=unused/i.weight
            real_value=i.density*unused
            total_value+=real_value
            res.append([i.weight,i.value,ratio])
    p='weight,value,portion\n'
    for w,v,r in res:
        p+=f'{w}  ,  {v},  {r}\n'
    p+=f'total value: {total_value}'
    return p

products=[Item(20,100),Item(30,120),Item(10,60)]
print(FindMaxCom(products,50))
>> weight,value,portion
    10  ,  60,  1
    20  ,  100,  1
    30  ,  120,  0.6666666666666666
    total value: 240.0

參考資料:
The Complete Data Structures and Algorithms Course in Python (from Udemy)