貪婪法_找零錢問題

貪婪法 (Greedy Algorithm)

貪心演算法
尋找問題最優解之方法

一般會將問題求解過程分割成若干個步驟(對問題進行拆解)

並在每個步驟都應用Greedy原則

選擇目前狀態下最好or最優的選擇(選擇傾向於局部最有利的概念)


Step1. 建立數學模型(最優解模型)
Step2. 問題分解一系列子問題 並同時定義子問題最優解
Step3. 應用貪心原則確定每個子問題之局部最優解
           根據最優解模型，將子問題的局部最優解堆疊出全域最優解




某國發行的貨幣

總共有 25分 、 10分 、 5分、1分


四種貨幣



假設你是銷售員

要找給客戶41分錢 硬幣


要如何安排才可使找給客人的錢正確且硬幣個數最少


這個經典問題的子問題定義


即是  從  四種 幣值的硬幣中選擇一枚
使它和其他已經選擇的硬幣幣值總額不超過  41分錢

使用貪婪策略進行下
【以幣值總額不超過41為前提，我們優先選擇幣值大者進行擺放】
我們會選擇   最大幣值去

step1.  25
step2.  10
step3.  5
step4.  1


total:41 ---> 總共 四個硬幣

此為本問題之   最優解


無最優解的情況探討

某國發行的貨幣

總共有 25分 、 20分 、 5分、1分


四種貨幣

這時最優策略

2個 20分    1  個  1分

總共     3個硬幣



用貪婪得到的則是


1個25分    3  個  5分    1個 1分

總共    5個硬幣