貪心算法是什么

1 概念

貪心的意思在于在作出選擇時(shí)，每次都要選擇對(duì)自身最為有利的結(jié)果，保證自身利益的最大化。貪心算法就是利用這種貪心思想而得出一種算法。

貪心算法作為五大算法之一，在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用十分廣泛。例如：在求最小生成樹(shù)的 Prim 算法中，挑選的頂點(diǎn)是候選邊中權(quán)值最小的邊的一個(gè)端點(diǎn)。在 Kruskal 算法中，每次選取權(quán)值最小的邊加入集合。在構(gòu)造霍夫曼樹(shù)的過(guò)程中也是每次選擇最小權(quán)值的節(jié)點(diǎn)構(gòu)造二叉樹(shù)。這種每次在執(zhí)行子問(wèn)題的求解時(shí)，總是選擇當(dāng)前最優(yōu)的情形，恰好符合貪心的含義。

貪心算法可以簡(jiǎn)單描述為：大事化小，小事化了。對(duì)于一個(gè)較大的問(wèn)題，通過(guò)找到與子問(wèn)題的重疊，把復(fù)雜的問(wèn)題劃分為多個(gè)小問(wèn)題。并且對(duì)于每個(gè)子問(wèn)題的解進(jìn)行選擇，找出最優(yōu)值，進(jìn)行處理，再找出最優(yōu)值，再處理。也就是說(shuō)貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。

貪心算法在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

2 算法流程

??（1）建立數(shù)學(xué)模型來(lái)描述問(wèn)題。
??（2）把求解的問(wèn)題分成若干個(gè)子問(wèn)題。
??（3）對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。
??（4）把子問(wèn)題的局部最優(yōu)解合成原來(lái)問(wèn)題的一個(gè)解。

3 偽代碼

從問(wèn)題的某一初始解出發(fā)
    while (能朝給定總目標(biāo)前進(jìn)一步) 
        do
            選擇當(dāng)前最優(yōu)解作為可行解的一個(gè)解元素；
    由所有解元素組合成問(wèn)題的一個(gè)可行解。

4 示例

題目描述：

小明手中有 1，5，10，50，100 五種面額的紙幣，每種紙幣對(duì)應(yīng)張數(shù)分別為 5，2，2，3，5 張。若小明需要支付 456 元，則需要多少?gòu)埣垘牛?/p>

 

題目分析

（1）建立數(shù)學(xué)模型
??設(shè)小明每次選擇紙幣面額為 Xi ，需要的紙幣張數(shù)為 n 張，剩余待支付金額為 V ，則有：
X1 + X2 + … + Xn = 456.
（2）問(wèn)題拆分為子問(wèn)題
??小明選擇紙幣進(jìn)行支付的過(guò)程，可以劃分為n個(gè)子問(wèn)題：即每個(gè)子問(wèn)題對(duì)應(yīng)為：
在未超過(guò)456的前提下，在剩余的紙幣中選擇一張紙幣。
（3）制定貪心策略，求解子問(wèn)題

制定的貪心策略為：在允許的條件下選擇面額最大的紙幣。則整個(gè)求解過(guò)程如下：

• 選取面值為 100 的紙幣，則 X1 = 100, V = 456 - 100 = 356；

• 繼續(xù)選取面值為 100 的紙幣，則 X2 = 100, V = 356 - 100 = 256；

• 繼續(xù)選取面值為 100 的紙幣，則 X3 = 100, V = 256 - 100 = 156；

• 繼續(xù)選取面值為 100 的紙幣，則 X4 = 100, V = 156 - 100 = 56；

• 選取面值為 50 的紙幣，則 X5 = 50, V = 56 - 50 = 6；

• 選取面值為 5 的紙幣，則 X6 = 5, V = 6 - 5 = 1；

• 選取面值為 1 的紙幣，則 X7 = 1, V = 1 - 1 = 0；求解結(jié)束

（4）將所有解元素合并為原問(wèn)題的解

小明需要支付的紙幣張數(shù)為 7 張，其中面值 100 元的 4 張，50 元 1 張，5 元 1 張，1 元 1 張。

代碼實(shí)現(xiàn)

const int N = 5; 
int Count[N] = {5,2,2,3,5};//每一張紙幣的數(shù)量 
int Value[N] = {1,5,10,50,100};
int solve(int money) {
    int num = 0;
    for(int i = N-1;i>=0;i--) {
        int c = min(money/Value[i],Count[i]);//每一個(gè)所需要的張數(shù) 
        money = money-c*Value[i];
        num += c;//總張數(shù) 
    }
    if(money>0) num=-1;
    return num;
}