什么是貪心算法虑啤？
貪心算法并不是一個具體的算法，而是一種算法的思想睬塌，或者說是解決問題一種思路灾梦。這就有兩個關(guān)鍵的點，可以解釋貪心算法：
- 貪心算法解決什么問題？
- 貪心算法是怎樣的一種思路？
1. 貪心算法解決什么問題
解決求最優(yōu)解問題。即此問題的最終的目的邪码，是為了得到一個最優(yōu)解。比如咬清，從A地到B地之間的最短路徑闭专，100塊錢可以在一個商場里買到的東西最多，等等之類的旧烧。
2. 貪心算法是怎樣的一種思路
顧名思義影钉，貪心算法，是一種很“貪”的算法掘剪。它的整體步驟平委，可以歸納為：
- 將問題分解成多個小問題或者多個步驟。
- 在每個小問題或者步驟中夺谁，執(zhí)行某種最優(yōu)化策略廉赔，得到局部最優(yōu)解
- 所有每個步驟得到的最優(yōu)化解，組合得到全局最優(yōu)化解匾鸥，不回溯處理
貪心算法最大的特點蜡塌，就是在每一步中取最優(yōu)化的解，不會回溯處理勿负。這樣的策略馏艾，自然在執(zhí)行速度上更快，但是因為這種方法的短視。會導致得的解并不是真正的全局最優(yōu)解琅摩，但是貪心算法得到的依然是一個近似最優(yōu)解铁孵。
0-1背包問題
問題可以描述為：給定一組物品，每種物品都有自己的重量和價格房资，在限定的總重量內(nèi)蜕劝，我們?nèi)绾芜x擇，才能使得物品的總價格最高志膀。
通俗解釋：假如你有一個只能承重100的背包熙宇，你往里面裝一些重量和價值不等的東西鳖擒，怎樣才可以讓你的背包中的價值最大溉浙。
這個問題中就是關(guān)鍵在于，每個轉(zhuǎn)入背包的東西蒋荚，只能是被裝入背包和不被裝入背包兩種狀態(tài)戳稽，可以用0-1表示。所以叫0-1背包問題期升。其二惊奇，就是這個問題的兩個限定。第一播赁，背包的邊界是明確颂郎，它只能承重那么多東西。第二容为，東西的邊界是明確的乓序，你只有那么一些東西可以選擇。
故而坎背，這個問題其實有三種策略可以選擇：
- 每次裝入的都是價值和重量比率最高的替劈，也就是我們常說的性價比最高的
- 每次裝入的是當前可選擇的東西中，價值最高的
- 每次裝入的是當前可選擇東西中得滤，重量最輕的
這三種策略中陨献，策略一看起來最好的策略。但是懂更，策略一的模糊化太大眨业，需要根據(jù)特殊的情況，做出特殊的改變沮协。
策略二和策略三相同龄捡，本身上并沒有太多不同。只是二者的視角不同皂股。
我基于第三種策略墅茉，給出python的實現(xiàn)。（人生苦短，我用python就斤『纺迹看不慣來打我呀~~）
#-*-coding:utf-8-*-
#0-1背包問題的實現(xiàn)
class Good:
def __init__(self, weight, value, status):
self.weight = weight
self.value = value
self.status = status # 0未選中，1已選中
#@param goods 物品的集合
#@param total 背包的空閑重量
def greed(goods, total):
result = []
while True:
s=strategy(goods,total)
if s == -1:
break;
result.append(goods[s].weight)
total = total - goods[s].weight
goods[s].status = 1
return result
#策略
def strategy(goods,total):
index = -1
minWeight = goods[0].weight
for i in range(0, len(goods)):
currentGood = goods[i]
if currentGood.status == 0 and currentGood.weight <= total and currentGood.weight <= minWeight :
index = i
minWeight = goods[index].weight
return index
