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

貪心算法并不保證會得到最優(yōu)解，但是在某些問題上貪心算法的解就是最優(yōu)解。要會判斷一個問題能否用貪心算法來計算。貪心算法和其他算法比較有明顯的區(qū)別，動態(tài)規(guī)劃每次都是綜合所有問題的子問題的解得到當前的最優(yōu)解(全局最優(yōu)解)，而不是貪心地選擇;回溯法是嘗試選擇一條路，如果選擇錯了的話可以“反悔”，也就是回過頭來重新選擇其他的試試。

[[280667]]

1 找零問題

假設商店老板需要找零 n 元錢，錢幣的面額有100元，50元，20元，5元，1元，如何找零使得所需錢幣的數(shù)量最少?(注意：沒有10元的面額)

那要是找376元零錢呢? 100*3+50*1+20*1+5*1+1*1=375

代碼如下：

# t表示商店有的零錢的面額 
t = [100, 50, 20, 5, 1] 
  
# n 表示n元錢 
def change(t, n): 
 m = [0 for _ in range(len(t))] 
 for i, money in enumerate(t): 
 m[i] = n // money # 除法向下取整 
 n = n % money # 除法取余 
 return m, n 
  
print(change(t, 376)) # ([3, 1, 1, 1, 1], 0) 

2 背包問題

常見的背包問題有整數(shù)背包和部分背包問題。那問題的描述大致是這樣的。

一個小偷在某個商店發(fā)現(xiàn)有 n 個商品，第 i 個商品價值 Vi元，重 Wi 千克。他希望拿走的價值盡量高，但他的背包最多只能容納W千克的東西。他應該拿走那些商品?

• 0-1背包：對于一個商品，小偷要么把他完整拿走，要么留下。不能只拿走一部分，或把一個商品拿走多次(商品為金條)
• 分數(shù)背包：對于一個商品，小偷可以拿走其中任意一部分。(商品為金砂)

舉例： 

對于 0-1 背包 和 分數(shù)背包，貪心算法是否都能得到最優(yōu)解?為什么?

顯然，貪心算法對于分數(shù)背包肯定能得到最優(yōu)解，我們計算每個物品的單位重量的價值，然后將他們降序排序，接著開始拿物品，只要裝得下全部的該類物品那么就可以全裝進去，如果不能全部裝下就裝部分進去直到背包裝滿為止。

而對于此問題來說，顯然0-1背包肯定裝不滿。即使偶然可以，但是也不能滿足所有0-1背包問題。0-1背包(又叫整數(shù)背包問題)還可以分為兩種：一種是每類物品數(shù)量都是有限的(bounded)。一種是數(shù)量無限(unbounded)，也就是你想要的多少有多少，這兩種都不能使用貪心策略。0-1背包是典型的第一種整數(shù)背包問題。

分數(shù)背包代碼實現(xiàn)：

# 每個商品元組表示（價格，重量） 
goods = [(60, 10), (100, 20), (120, 30)] 
# 我們需要對商品首先進行排序，當然這里是排好序的 
goods.sort(key=lambda x: x[0]/x[1], reverse=True) 
  
# w 表示背包的容量 
def fractional_backpack(goods, w): 
 # m 表示每個商品拿走多少個 
 total_v = 0 
 m = [0 for _ in range(len(goods))] 
 for i, (prize, weight) in enumerate(goods): 
 if w >= weight: 
 m[i] = 1 
 total_v += prize 
 w -= weight 
 # m[i] = 1 if w>= weight else weight / w 
 else: 
 m[i] = w / weight 
 total_v += m[i]*prize 
 w = 0 
 break 
 return m, total_v 
  
res1, res2 = fractional_backpack(goods, 50) 
print(res1, res2) # [1, 1, 0.6666666666666666] 
1.3 拼接最大數(shù)字問題 

有 n 個非負數(shù)，將其按照字符串拼接的方式拼接為一個整數(shù)。如何拼接可以使得得到的整數(shù)最大?

例如：32， 94， 128， 1286， 6， 71 可以拼接成的最大整數(shù)為 94716321286128.

注意1：字符串比較數(shù)字大小和整數(shù)比較數(shù)字大小不一樣!!! 字符串比較大小就是首先看第一位，大的就大，可是一個字符串長，一個字符串短如何比較呢?比如128和1286比較

思路如下：

# 簡單的：當兩個等位數(shù)相比較

a = '96' 
b = '97' 
  
a + b if a > b else b + a 

# 當出現(xiàn)了下面的不等位數(shù)相比較，如何使用貪心算法呢?

# 我們轉化思路，拼接字符串，比較結果

 a = '128' 
b = '1286' 
 # 字符串相加 
a + b = '1281286' 
b + a = '1286128' 
  
a + b if a + b > b + a else b + a 

數(shù)字拼接代碼如下：

from functools import cmp_to_key 
  
li = [32, 94, 128, 1286, 6, 71] 
  
def xy_cmp(x, y): 
 # 其中1表示x>y，-1,0同理 
 if x+y < y+x: 
 return 1 
 elif x+y > y+x: 
 return -1 
 else: 
 return 0 
  
def number_join(li): 
 li = list(map(str, li)) 
 li.sort(key=cmp_to_key(xy_cmp)) 
 return "".join(li) 
  
print(number_join(li)) # 94716321286128 

4 活動選擇問題

假設有 n 個活動，這些活動要占用同一片場地，而場地在某時刻只能供一個活動使用。

每一個活動都有一個開始時間 Si 和結束時間 Fi (題目中時間以整數(shù)表示)表示活動在 [Si, fi) 區(qū)間占用場地。(注意：左開右閉)

問：安排哪些活動能夠使該場地舉辦的活動的個數(shù)最多? 

貪心結論：最先結束的活動一定是最優(yōu)解的一部分。

證明：假設 a 是所有活動中最先結束的活動，b是最優(yōu)解中最先結束的活動。

如果 a=b，結論成立

如果 a!=b，則 b 的結束時間一定晚于 a 的結束時間，則此時用 a 替換掉最優(yōu)解中的 b ，a 一定不與最優(yōu)解中的其他活動時間重疊，因此替換后的解也是最優(yōu)解。

代碼如下：

# 一個元組表示一個活動，（開始時間，結束時間） 
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), 
 (8, 12), (2, 14), (12, 16)] 
  
# 保證活動是按照結束時間排好序,我們可以自己先排序 
activities.sort(key=lambda x:x[1]) 
  
def activity_selection(a): 
 # 首先a[0] 肯定是最早結束的 
 res = [a[0]] 
 for i in range(1, len(a)): 
 if a[i][0] >= res[-1][1]: # 當前活動的開始時間小于等于最后一個入選活動的結束時間 
 # 不沖突 
 res.append(a[i]) 
 return res 
  
res = activity_selection(activities) 
print(res) 

5 最大子序和

求最大子數(shù)組之和的問題就是給定一個整數(shù)數(shù)組(數(shù)組元素有負有正)，求其連續(xù)子數(shù)組之和的最大值。下面使用貪心算法逐個遍歷。

代碼如下：

def maxSubarray(li): 
 s_max, s_sum = 0, 0 
 for i in range(len(li)): 
 s_sum += li[i] 
 s_max = max(s_max, s_sum) 
 if s_sum < 0: 
 s_sum = 0 
  
 return s_max