算法小專欄：貪心算法

貪心算法，又稱「貪婪算法」。 在對問題求解時，總是做出在當前看來是最好的選擇。（局部最優解） 也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的 局部最優解 。 貪心算法不是對所有問題都能得到整體最優解，但對範圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的 近似解 。（來源360百科）

註：貪心算法是一種高性能算法，複雜度低，簡單易用。 貪心算法求出來的結果不一定都是最優解。對於某些問題，它能求出最優解。而還有些問題，它能求出最優解的**「近似解」**。

二、算法思想

「大事化小，小事化了」。

• 大事化小：一個較大的問題，通過找到與子問題的重疊，把複雜的問題劃分為多個小問題；
• 小事化了：從小問題找到決策的核心，確定一種局部最優解的策略。
• 通過計算出局部的最優解，來推出全局的最優解或近似解。

偽代碼如下：

從問題的某一初始解出發
 while (能朝給定總目標前進一步) 
 do
 選擇當前最優解作為可行解的一個解元素；
 由所有解元素組合成問題的一個可行解。
複製代碼

三、找零問題

這是一個求得 最優解 的貪心算法例子。

場景：一名收銀員，需要找零 88 元。 怎麼找零，所需要的紙/硬幣的數量最少。

思路：依次找最大的紙幣， 例如：找零88元， ¥88 = ¥50 + ¥20 + ¥10 + ¥5 + ¥1 * 3

# arr的每一位：分別對應100塊、50塊、20塊、10塊、5塊、1塊紙幣。
arr = [0,0,0,0,0,0]

def change(money):
 while money >= 1:
 if money >= 100:
 money -= 100
 arr[0] += 1
 elif money >= 50:
 money -= 50
 arr[1] += 1
 elif money >= 20:
 money -= 20
 arr[2] += 1
 elif money >= 10:
 money -= 10
 arr[3] += 1
 elif money >= 5:
 money -= 5
 arr[4] += 1
 elif money >= 1:
 money -= 1
 arr[5] += 1

change(88)
print arr
複製代碼

結果輸出：

四、0-1背包問題

這是一個求得最優解的 近似解 的貪心算法例子。 而如果要想求得最優解，就要用到DP策略。而動態規劃將在 下篇 介紹。

場景：一個小偷去商場偷東西，在背包稱重有限下，如何拿能使得獲得收益越大？（每件商品只有一個，只能選擇拿與不拿）

• 貪心策略1：每次取當前能拿得下的 最值錢 的商品。
• 貪心策略2：每次取當前重量 最輕 的商品。
• 貪心策略3：每次取 性價比最高 的商品。（即 價格/重量 的值最大的商品）

接下來我們依次分析，並且找出不是最優解的反例。

貪心策略1：選取價值最大的商品。

反例： 背包最大重量 W = 4kg

商品價格重量商品A3000元4kg商品B2000元3kg商品C1500元1kg

根據策略，首先選取商品A，接下來就無法再選取了，可是明明選取商品B、C更好。

貪心策略2：選取重量最輕的商品。

與策略1類似，舉反例： 背包最大重量 W = 4kg

商品價格重量商品A3500元4kg商品B2000元3kg商品C1000元1kg

根據策略，首先選取商品C，接下來選取商品B，可是明明選取A更好。