貪心算法

1. 前言

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

2. 什么是貪心算法？

貪心算法（Greedy Algorithm）是計算機科學與技術領域中一種常見的選擇算法，與之前介紹的動態規劃算法有一定的相似度。

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

貪心算法與動態規劃算法的最大區別在于：貪心算法每次選擇的時候都是按照貪心策略來選擇的，滿足當前情況的最優解，但是并不一定會是整體最優解；動態規劃算法在選擇考慮時會考慮所有的子情況，選擇最優解，這會是整體的最優解。

3. 貪心算法的使用條件

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

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

對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。

2. 最優子結構： 如果一個問題的最優解包含其子問題的最優解，則此問題具備最優子結構的性質。問題的最優子結構性質是該問題是否可以用貪心算法求解的關鍵所在。

貪心算法與動態規劃算法求解的問題類似，都需要滿足最優子結構的性質。

4. 貪心算法的應用場景

在日常的生活學習中，貪心算法一般可以用來解決很多實際問題?，F在，我們就來看看貪心算法具體有哪些應用場景。

場景 1：活動選擇問題

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

面對這樣的問題，其實在日常生活中，我們的第一選擇肯定是先把結束時間早的兼職活動做了，然后再去做其他的兼職？這里面其實就是有貪心思想的應用，因為我們每次都是先做完結束時間早的兼職，然后我們會留出更多的時間可以做其他兼職。

這個問題里面的貪心選擇就是每次選擇最先結束的兼職活動，并且可以證明每次選擇的最先結束的兼職活動是整體最優的，因為如果不是選擇最先結束的兼職活動，剩下的可兼職的時間就少了，可以完成的兼職也就少了。同樣，兼職選擇活動具備最優子結構的性質，子問題可以選擇的最多兼職在整體問題中同樣適用。

場景 2：錢幣找零問題

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

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

我們可以很明顯的發現，貪心算法很多時候都是應用于求解一些最優化問題，與動態規劃算法很相似，這類問題在現實生活或者學習科研中經常會遇到，這是一種解決問題的思路與方法，希望大家可以好好思考。

5. 小結

本節主要介紹了貪心算法的定義及基本概念，在學完本節課程之后，需要明白什么樣的問題適合利用貪心算法求解，如何自己去設計一個貪心算法，以及我們日常生活中哪些應用場景適合用貪心算法思想求解。