“所謂貪心算法堤尾，就是不斷地選取當(dāng)前最優(yōu)策略的方法設(shè)計(jì)算法。在問題求解時(shí)迁客，總是做出現(xiàn)在看起來是最好的選擇郭宝。”
?
關(guān)于貪心算法，沒什么好說的掷漱，因?yàn)樗鼪]有固定的算法框架粘室，本文通過幾個(gè)問題的解決來介紹下貪心算法以及該算法的應(yīng)用。
︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿
田忌賽馬
田忌賽馬的故事大家都聽過卜范。講的是孫臏為田忌調(diào)整了作戰(zhàn)策略衔统，使得整體實(shí)力較弱的田忌的馬戰(zhàn)勝了實(shí)力較強(qiáng)的齊威王的馬。策略也很簡(jiǎn)單先朦，總共就分上中下三等馬缰冤，用下等馬對(duì)戰(zhàn)齊王的上等馬，上等馬對(duì)戰(zhàn)齊王的中等馬喳魏，中等馬對(duì)戰(zhàn)齊王的下等馬棉浸，這樣明明整體實(shí)力較弱，但也能通過總比分2:1贏得比賽刺彩。
齊王比賽輸了之后迷郑，很不服氣，他認(rèn)為區(qū)區(qū)三匹馬的比較勝負(fù)只是運(yùn)氣罷了创倔。于是嗡害，它便拿出了整個(gè)馬場(chǎng)的馬要再和田忌比一次，并告訴田忌贏一局贏200金畦攘，輸一局輸200金霸妹，平局就不用出錢，并且給了田忌三天時(shí)間考慮知押。田忌有了上次孫臏的策略之后叹螟，決定自己設(shè)計(jì)策略。
假設(shè)田忌知道自己和齊王的所有的馬的跑的快慢的等級(jí)台盯，該如何設(shè)計(jì)策略罢绽，使得田忌盡量多贏錢或者盡量少輸錢。
我們結(jié)合貪心算法這個(gè)名稱和這個(gè)比賽來分析一下問題静盅。所謂貪心算法的宗旨就是一個(gè)字-----貪良价。放到上面例子中，就是盡可能贏多的錢。而當(dāng)我們拿到一匹馬明垢，怎么才能讓這匹馬為我們盡可能多的贏'錢'蚣常，或者說創(chuàng)造盡可能多的價(jià)值呢。就算不能創(chuàng)造己方的直接價(jià)值袖外，也要讓對(duì)方消耗最多的價(jià)值史隆。回到題目就是曼验，如果這匹馬有能贏過的對(duì)手馬，就選擇能贏過的馬當(dāng)中最高等級(jí)的一匹粘姜。如果這匹馬遇上誰(shuí)都是輸鬓照，那就選擇對(duì)手馬中最強(qiáng)的一匹，死也要拉個(gè)墊背的孤紧。我們要做的是貪豺裆，榨干每匹馬的價(jià)值，這就是貪心的本質(zhì)号显。
?
為了復(fù)雜度臭猜，我們可以對(duì)雙方的馬先進(jìn)行一個(gè)排序，然后按順序比較過去押蚤，talk is cheap蔑歌， 我們來看看偽代碼。
?int main()
{
????1.輸入你和齊王所有的馬匹(共n匹)速度等級(jí)揽碘，你的存放在數(shù)組vl1,????齊王的存放在vl2中,累計(jì)的錢存放在sum中
????2.將vl1,vl2降序排序
????3.遍歷你的馬匹次屠，逐一與齊王的作比較
????for?(i?=?0;?i?<?n;?i++)
????{
????????/*?標(biāo)識(shí)是否有能戰(zhàn)勝的馬?*/
????????int?flag = 0;
????????for?(j?=?0;?j?<?n;?j++)
????????{
????????? ? /* 若齊王的這匹馬比過，跳過 */
????????????if?(vl2[j]?==?-1)??continue;
????????????/* 若比齊王的快雳刺，標(biāo)記flag */
????????????if?(vl1[i]?>?vl2[j])
????????????{
????????????????flag = 1;
????????????????//?因?yàn)轫樞蚺帕羞^劫灶，所以最先能贏的就是能贏的
????????????????//?當(dāng)中最強(qiáng)的，比較后將速度置為-1掖桦，認(rèn)為這兩匹
????????????????//?是比過的本昏，后面不再使用。
????????????????vl1[i]?=?-1; vl2[j]?=?-1;
????????????????break;
????????????}
????????}
????????if?(flag?==?1)
????????? sum += 200枪汪；
????????/*?此時(shí)說明你剩余最快的馬已經(jīng)不比齊王最慢的馬快了,???????????也就是你之后所有的馬要么打平要么輸了涌穆。?*/
????????else
????????{
????????????/*?若最快的馬已經(jīng)比齊王最慢的還慢了，直接扣錢料饥，????????????否則標(biāo)記馬匹蒲犬，就當(dāng)無(wú)事發(fā)生?*/
????????????if?(vl1[i]?<?vl2[n-1-i])
????????????{
??????????????? sum -= 200;
????????????}
????????????vl1[i] = -1; vl2[n-1-i] = -1;
????????}
????}
????4. 輸出結(jié)果sum
?? ? return 0;
}
大致的程序就如上所示，事實(shí)上上述代碼效率還是很低下的岸啡，時(shí)間復(fù)雜度為O(n^2)原叮，可以通過每次修改比較的位置使復(fù)雜度達(dá)到O(n)。不過這邊主要介紹貪心的思想，所以不拓展講其他解法和優(yōu)化寫法了奋隶。
︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿︿
均分紙牌
這也是一道貪心的經(jīng)典例題擂送，雖然它貪心的不那么明顯。
描述：
有n堆紙牌唯欣，編號(hào)分別為 1嘹吨，2，…, n境氢。每堆上有若干張蟀拷，但紙牌總數(shù)必為n的倍數(shù)∑剂模可以在任一堆上取若干張紙牌问芬，然后移動(dòng)。移牌規(guī)則為：在編號(hào)為1的堆上取的紙牌寿桨，只能移到編號(hào)為 2 的堆上此衅；在編號(hào)為 n 的堆上取的紙牌，只能移到編號(hào)為n-1的堆上亭螟；其他堆上取的紙牌挡鞍，可以移到相鄰左邊或右邊的堆上。現(xiàn)在要求找出一種移動(dòng)方法预烙，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多墨微。
例如 n=4，4堆紙牌數(shù)分別為：?
① 9∧椤② 8』逗佟③ 17 ④ 6
移動(dòng)3次可達(dá)到目的：
從 ③ 取4張牌放到④（9 8 13 10）->
從③取3張牌放到 ②（9 11 10 10）->
從②取1張牌放到①（10 10 10 10）也糊。
思路：
1炼蹦、題目中說了紙牌總數(shù)是n的倍數(shù)，那么平均值必為整數(shù)狸剃。
2掐隐、因?yàn)橹荒軓南噜彽呐贫涯门疲乙笞钌俅螖?shù)钞馁。所以得一次移動(dòng)到位虑省，不能來回勻。按照貪心思想（移動(dòng)盡可能少的次數(shù)的情況）僧凰，就是讓當(dāng)前牌堆一次移動(dòng)就達(dá)到目標(biāo)牌堆數(shù)（即平均數(shù)）探颈，缺多少就一次直接從邊上拿多少。所以一開始训措，就把目標(biāo)數(shù)定為最終需要達(dá)到的平均數(shù)就是本題的貪心思想伪节。
3光羞、我們邏輯上從左往右遍歷，如果當(dāng)前牌堆數(shù)量就是平均值怀大，繼續(xù)下一堆纱兑。如果不是平均值，我們邏輯上一定是從右邊拿牌化借，拿的牌數(shù)為(平均值 - a[i])潜慎，即使拿的牌數(shù)是負(fù)的也沒關(guān)系，因?yàn)檎?fù)僅僅表示拿進(jìn)或者拿出蓖康。這樣就不用考慮再?gòu)淖筮厔虻那闆r铐炫，因?yàn)樽筮叺囊呀?jīng)之前給了你，你只需要一路往前就行了蒜焊。
代碼如下：
int main()
{
???int?n,?i,?sum,?average;
???/*?輸入牌堆數(shù)和每堆牌的牌數(shù)?*/
???scanf("%d",?&n);
???for?(i?=?0;?i?<?n;?i++)
???{
???? ? scanf("%d", &a[i]);
???????sum += a[i];
???}
???/*?求得牌的平均值?*/
???average = sum / n;
???int?step = 0;
??????/* 遍歷牌堆 */
???for?(i?=?0;?i?< n; i++)
???{
???? ? if (a[i] == average)
???????????continue;
???????/*?只能從相鄰牌堆取驳遵，所以將需要的牌數(shù)傳給下一堆?*/
???????a[i?+?1]?-= average - a[i];
???????step?++;
???}
??????printf("%d\n",?step);
???return?0;
}
