貪心算法,一文搞懂

前言

今天學(xué)習(xí)一下貪心算法，從字面意思大概能體會(huì)到，這個(gè)算法的大致意思。

"貪心" 這個(gè)詞大家都懂，就是總想要最好的，說明這個(gè)人比較貪嘛。貪心算法也屬于五大常用算法之一。

? ?

基本概念

貪心算法是指，在對問題求解時(shí)，總是做出在當(dāng)前看來，是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅僅是在，某種意義上的局部最優(yōu)解。

貪心算法注重，貪心策略的選擇。必須注意的是，貪心算法不是對所有問題，都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性。

即某個(gè)狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。所以，對所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性。

解題思路

下面看一下，使用貪心算法，解決問題的幾個(gè)例子。

跳躍游戲

題目：
定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。數(shù)組中的每個(gè)元素代表，你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)位置。

輸入：? [2, 3, 1, 1, 4]

輸出：true

解釋: 我們可以先跳 1 步，從位置 0 到達(dá) 位置 1，?然后再從位置 1 跳 3 步，到達(dá)最后一個(gè)位置。

思路：貪心算法，每次找到可跳范圍內(nèi)的，數(shù)組值的最大值，看通過這個(gè)最大值，能否跳到尾部。不能跳到尾部，則遍歷下一個(gè)，然后重復(fù)上述操作。

bool?canJump(vector<int>&?nums)?{
???int?n?=?nums.size();
???//最遠(yuǎn)可以到達(dá)的地方??
???int?rightmost?=?0;??

???//遍歷數(shù)組
???for?(int?i?=?0;?i?<?n;?++i)?{
??????if?(i?<=?rightmost)?{
??????????//如果較大值可以到達(dá)，則說明可以到達(dá)
??????????rightmost?=?max(rightmost,?i?+?nums[i]);
??????????if?(rightmost?>=?n?-?1)?{
??????????????return?true;
??????????}
??????}
???}
??return?false;
}

會(huì)場安排問題

題目：
會(huì)場用來安排活動(dòng)，每個(gè)活動(dòng)，有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間。在某個(gè)活動(dòng)的開始時(shí)間，到結(jié)束時(shí)間這段范圍內(nèi)，其他活動(dòng)不能再被安排，求最多能安排多少場活動(dòng)。

#include<stdio.h>
#include<stdlib.h>
?
void?GreedySelector(int?n,int?s[],int?f[],int?A[]){
?   int?i, j;
?   //第一個(gè)活動(dòng)要選，第一個(gè)結(jié)束時(shí)間最短,A[i]=1表示第i個(gè)活動(dòng)入選
?   A[1] = 1;
?   //j=1表示取第一個(gè)活動(dòng)的結(jié)束時(shí)間
?   j = 1;
?
?   //用i遍歷每個(gè)活動(dòng)
?   for(i = 2; i <= n; i++){?
??      //這個(gè)活動(dòng)的開始時(shí)間小于上個(gè)活動(dòng)的結(jié)束時(shí)間
??      if(s[i] > f[j]){
???         A[i] = 1;
???         j = i;
??      } else {
???         A[i] = 0;
??      }
?   }
}
?
int?main(){
?   int?i;
?   //每個(gè)活動(dòng)按活動(dòng)的結(jié)束時(shí)間進(jìn)行排序
?   //活動(dòng)的開始時(shí)間
?   int?s[]?=?{0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
?   //活動(dòng)的結(jié)束時(shí)間
?   int?f[]?=?{0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};?
?   int?n=11, A[11];
?
?   GreedySelector(n, s, f, A);
?   for(i = 1; i <= n; i++){
??     if(A[i]?==?1){
???        printf("%d\n", i);
??     }
?   }
   ?return?0;
}

運(yùn)行結(jié)果：1 ? 4 ?8 ?11，這 4 個(gè)下標(biāo)對應(yīng)的活動(dòng)。

策略選擇：

• 開始時(shí)間最早優(yōu)先（證明不可行）??

• 占用時(shí)間少優(yōu)先(證明不可行)??

• 結(jié)束時(shí)間最早優(yōu)先(使用貪心算法可以得到最優(yōu)解)

加油站問題

題目：
一個(gè)汽車加滿油后可以行使n千米，圖中會(huì)經(jīng)過一系列加油站，求到達(dá)最終加油的最少次數(shù)，給出每個(gè)加油站之間的距離。

#include<stdio.h>
//n表示汽車加滿油后可以行使nkm
#define?n?7?
?
int?main()
{
?    int?a[n?+?1]?=?{1, 2, 3, 4, 5, 1, 6, 6};
?????//k表示途中有k個(gè)加油站?
?    int?k?=?7;
?????//油箱里的剩余油量，在起點(diǎn)時(shí)油量是滿的
?    int?rest?=?7;
?    int?count?=?0;
?    int?i?=?0;
?
?    //n表示加滿油可以行使n千米
?    while(i?<?n?+?1){
??       //當(dāng)前行程>rest
??       if(a[i]?>?rest){
???          //加油
???          count?++;
???          //重新賦值rest
???          rest?=?n;
??       }
??
??       rest?-=?a[i];
??       printf("rest=%d,i=%d\n", rest, i);
??       i?++;
?    }
?
?   printf("the?mininum?is?%d.", count);
?   return?0;
}

每到一個(gè)加油站時(shí)，判斷當(dāng)前的油量，能否開到下一個(gè)加油站，再?zèng)Q定是否加油，i 表示對應(yīng)的加油站。

貪心算法：局部最優(yōu)能推導(dǎo)出整體最優(yōu)，很容易，算法思維很常態(tài)化。

多次最優(yōu)服務(wù)次序問題

問題描述：

設(shè)有n 個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。每個(gè)顧客需要服務(wù)一定時(shí)間。共有s 處可以

提供此項(xiàng)服務(wù)。

應(yīng)如何安排n 個(gè)顧客的服務(wù)次序，才能使平均等待時(shí)間達(dá)到最小?平均等待時(shí)間是，n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。

編程任務(wù)：

對于給定的，n個(gè)顧客需要的服務(wù)時(shí)間和s的值，編程計(jì)算最優(yōu)服務(wù)次序。

#include<stdio.h>
#include<algorithm>
using?namespace?std;
?
//顧客數(shù)
#define?n?10?
//服務(wù)窗口數(shù)??
#define?s?2????

int?main()
{
??????//總共需要服務(wù)10位顧客，每位顧客需要服務(wù)的時(shí)間存在數(shù)組里
?     int?a[n]?=?{56, 12, 1, 99, 1000, 234, 33, 55, 99, 812};
?     int?i;
?     int?sum?=?0;
?
?     //服務(wù)窗口
?     int?sub[s]?=?{0};??
?     sort(a, a?+?n);

?     for(i?=?0; i?<?n; i?++){
??        sub[i?%?s]?+=?a[i];
??        sum?+=?sub[i?%?s];
?     }

?     printf("%.2f", sum?*?1.0?/?n);
?     return?0;?
}?

運(yùn)行打印：336.00?

0 號窗口服務(wù)1，33，56....

1 號窗口服務(wù)12，55，99...

對應(yīng) 0 號窗口，當(dāng)服務(wù) 1 時(shí)，后面幾位顧客需要等待的時(shí)間，就是前面幾位顧客需要的服務(wù)時(shí)間的累加，前面有多少顧客就需要累加多少次。1 號窗口也是一樣。

絮叨

··················?END?··················

點(diǎn)擊關(guān)注公眾號，免費(fèi)領(lǐng)學(xué)習(xí)資料

????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? 點(diǎn)“贊”和“在看”哦