貪心的人要會(huì)貪心算法
前言
今天學(xué)習(xí)一下貪心算法，從字面意思大概能體會(huì)到，這個(gè)算法的大致意思。
"貪心" 這個(gè)詞大家都懂，就是總想要最好的，說明這個(gè)人比較貪嘛。貪心算法也屬于五大常用算法之一。
基本概念
貪心算法是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來，是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅僅是在，某種意義上的局部最優(yōu)解。
貪心算法注重，貪心策略的選擇。必須注意的是，貪心算法不是對(duì)所有問題，都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性。
即某個(gè)狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。所以，對(duì)所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性。
解題思路
下面看一下，使用貪心算法，解決問題的幾個(gè)例子。
跳躍游戲
題目：
定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。數(shù)組中的每個(gè)元素代表，你在該位置可以跳躍的最大長(zhǎng)度。判斷你是否能夠到達(dá)最后一個(gè)位置。
輸入： [2, 3, 1, 1, 4]
輸出：true
解釋: 我們可以先跳 1 步，從位置 0 到達(dá) 位置 1， 然后再?gòu)奈恢?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ì)場(chǎng)安排問題
題目：
會(huì)場(chǎng)用來安排活動(dòng)，每個(gè)活動(dòng)，有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間。在某個(gè)活動(dòng)的開始時(shí)間，到結(jié)束時(shí)間這段范圍內(nèi)，其他活動(dòng)不能再被安排，求最多能安排多少場(chǎ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)對(duì)應(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 表示對(duì)應(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ù)：
對(duì)于給定的，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 號(hào)窗口服務(wù)1，33，56....
1 號(hào)窗口服務(wù)12，55，99...
對(duì)應(yīng) 0 號(hào)窗口，當(dāng)服務(wù) 1 時(shí)，后面幾位顧客需要等待的時(shí)間，就是前面幾位顧客需要的服務(wù)時(shí)間的累加，前面有多少顧客就需要累加多少次。1 號(hào)窗口也是一樣。
絮叨
貪心算法是一個(gè)很有趣的算法，場(chǎng)景適用于貪心算法，則解題非常容易。解題時(shí)需要明確，該題是否適用于貪心算法。
貪心算法在面試和工作也會(huì)有遇到的情況，希望大家結(jié)合本文弄懂此算法，后續(xù)相關(guān)算法知識(shí)，請(qǐng)見下期。
·················· END ··················
點(diǎn)擊關(guān)注公眾號(hào)，免費(fèi)領(lǐng)學(xué)習(xí)資料
點(diǎn)“贊”和“在看”哦