貪婪法_找零錢問題
貪婪法 (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個硬幣
貪心演算法
尋找問題最優解之方法
一般會將問題求解過程分割成若干個步驟(對問題進行拆解)
並在每個步驟都應用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分
四種貨幣
這時最優策略
總共 3個硬幣
用貪婪得到的則是
1個25分 3 個 5分 1個 1分
總共 5個硬幣
留言
張貼留言