貪心算法

1. 前言

本節(jié)內(nèi)容是貪心算法系列之一：貪心算法的介紹，主要介紹了貪心算法的定義，貪心算法的使用條件，明確了什么樣的問題適合用貪心算法求解，最后說明貪心算法在日常生活中的應(yīng)用場景。

2. 什么是貪心算法？

貪心算法（Greedy Algorithm）是計算機(jī)科學(xué)與技術(shù)領(lǐng)域中一種常見的選擇算法，與之前介紹的動態(tài)規(guī)劃算法有一定的相似度。

顧名思義，貪心算法總是會做出在當(dāng)前情況下看來最好的選擇，謂之貪心，也就是說貪心算法并不會從整體最優(yōu)考慮，它所做出的選擇都只是在某種意義上的局部最優(yōu)選擇。當(dāng)然貪心算法雖然不能對所有的問題得出整體最優(yōu)解，但是在很多問題中還是有著很好的應(yīng)用，可以得到整體的最優(yōu)解。

貪心算法與動態(tài)規(guī)劃算法的最大區(qū)別在于：貪心算法每次選擇的時候都是按照貪心策略來選擇的，滿足當(dāng)前情況的最優(yōu)解，但是并不一定會是整體最優(yōu)解；動態(tài)規(guī)劃算法在選擇考慮時會考慮所有的子情況，選擇最優(yōu)解，這會是整體的最優(yōu)解。

3. 貪心算法的使用條件

首先，在利用貪心算法求解問題之前，我們需要清楚什么樣的問題適合用貪心算法求解。一般而言，能夠利用貪心算法求解的問題都會具備以下兩點(diǎn)性質(zhì)：

1. 貪心選擇： 當(dāng)某一個問題的整體最優(yōu)解可通過一系列局部的最優(yōu)解的選擇達(dá)到，并且每次做出的選擇可以依賴以前做出的選擇，但不需要依賴后面需要做出的選擇。這就是貪心選擇性質(zhì)。

對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。

2. 最優(yōu)子結(jié)構(gòu)： 如果一個問題的最優(yōu)解包含其子問題的最優(yōu)解，則此問題具備最優(yōu)子結(jié)構(gòu)的性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題是否可以用貪心算法求解的關(guān)鍵所在。

貪心算法與動態(tài)規(guī)劃算法求解的問題類似，都需要滿足最優(yōu)子結(jié)構(gòu)的性質(zhì)。

4. 貪心算法的應(yīng)用場景

在日常的生活學(xué)習(xí)中，貪心算法一般可以用來解決很多實(shí)際問題?，F(xiàn)在，我們就來看看貪心算法具體有哪些應(yīng)用場景。

場景 1：活動選擇問題

假如小明是一個勤工儉學(xué)的在校生，每天可以兼職的時候有 10 個小時，然后現(xiàn)在學(xué)校有多個不同的兼職崗位，每個崗位有個開始時間和結(jié)束時間，小明在同一時間只能做一份兼職，請問小明每天最多可以做多少份的兼職？

面對這樣的問題，其實(shí)在日常生活中，我們的第一選擇肯定是先把結(jié)束時間早的兼職活動做了，然后再去做其他的兼職？這里面其實(shí)就是有貪心思想的應(yīng)用，因?yàn)槲覀兠看味际窍茸鐾杲Y(jié)束時間早的兼職，然后我們會留出更多的時間可以做其他兼職。

這個問題里面的貪心選擇就是每次選擇最先結(jié)束的兼職活動，并且可以證明每次選擇的最先結(jié)束的兼職活動是整體最優(yōu)的，因?yàn)槿绻皇沁x擇最先結(jié)束的兼職活動，剩下的可兼職的時間就少了，可以完成的兼職也就少了。同樣，兼職選擇活動具備最優(yōu)子結(jié)構(gòu)的性質(zhì)，子問題可以選擇的最多兼職在整體問題中同樣適用。

場景 2：錢幣找零問題

有 1 元、2 元、5 元、10 元的紙幣分別有若干張，要用這些紙幣湊出 m 元，至少要用多少張紙幣？

這個是生活中最為常見的一種場景，經(jīng)常我們在商場中用現(xiàn)金付款時，我們付出了 100 元，當(dāng)收銀員找零的時候，不知道大家有沒有發(fā)現(xiàn)，收銀員總是會先找零面額較大的貨幣，然后找零面額較小的貨幣，這個其實(shí)也是一個貪心選擇的過程，因?yàn)檫@樣可以保證找零的貨幣數(shù)量最少。

我們可以很明顯的發(fā)現(xiàn)，貪心算法很多時候都是應(yīng)用于求解一些最優(yōu)化問題，與動態(tài)規(guī)劃算法很相似，這類問題在現(xiàn)實(shí)生活或者學(xué)習(xí)科研中經(jīng)常會遇到，這是一種解決問題的思路與方法，希望大家可以好好思考。

5. 小結(jié)

本節(jié)主要介紹了貪心算法的定義及基本概念，在學(xué)完本節(jié)課程之后，需要明白什么樣的問題適合利用貪心算法求解，如何自己去設(shè)計一個貪心算法，以及我們?nèi)粘Ｉ钪心男?yīng)用場景適合用貪心算法思想求解。