典型應(yīng)用:優(yōu)化問題.? 一旦選中,便永遠(yuǎn)選定.
缺點(diǎn):實(shí)際中很多問題無法用此算法解決.
Demo 1:找零.
這個(gè)我想大家都學(xué)過,我就不寫了.
Demo 2: 日程安排.
2種情況,? 1:最小化任務(wù)的執(zhí)行時(shí)間
???????????????? 2:最大化收益.
我在這里說說最小化平均時(shí)間的算法.思路:每一步,從剩余的顧客中選出時(shí)間最少的顧客加到日程安排表里.
前提:顧客數(shù)量固定,每個(gè)顧客所需要的時(shí)間知道
算法:把顧客按照所需時(shí)間的升序排列.
下面證明此算法:?? 這個(gè)貪婪算法總是最優(yōu)的.
設(shè)P = p1,p2,p3.....pn 是從1到n的證書的任意一個(gè)排列,設(shè)si = tpi 如果顧客按照P 的順序進(jìn)行排列,則第i個(gè)可戶所需的時(shí)間為si .顧客所需的總時(shí)間為: T(p) = s1 + (s1+s2) +(s1+s2s3)+..........
????????????????????????????????????????????????????????????????????????? =? ns1+(n-1)s2+(n-2)s3+...........
???????????如果P不是按照整數(shù)的升序進(jìn)行的排列,那么可以找到2個(gè)整數(shù)a,b 使Sa?>Sb ,且a<b?
????????? 現(xiàn)在,我調(diào)換P中a,b的順序,則可求出另外一個(gè)總時(shí)間:T(p') = (n-a+1)Sb? + (n-b+1)Sa? +..........?其他的和T(P)一樣
??????????? T(p) -T(P')?> 0
???????????? 推出:可以改進(jìn)任何一個(gè)日程表,只要其中有某個(gè)顧客的服務(wù)順序優(yōu)于另外一個(gè)所需要的時(shí)間更少的,如果全按照升序,則無法改進(jìn),證明的出算法正確.????????????????????????????????????????????????????