數(shù)據(jù)結(jié)構(gòu)里面的貪心算法是什么?

貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)(即最有可能達(dá)到目標(biāo))的決策，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。貪心算法不能保證最優(yōu)解，但在解決問題的某些實例時是有效的，并且是很容易理解和實現(xiàn)的。

一個經(jīng)典的貪心算法示例是背包問題。假設(shè)你有一個容量為V的背包和n個物品，每個物品都有自己的價值和重量。問題是如何選擇物品，使得背包裝載的物品總價值最大。

貪心算法的做法是：每次選擇價值密度最高的物品（即價值/重量），直到背包裝滿為止。

這個算法并不能保證最優(yōu)解，但對于許多實例來說是有效的。

代碼示例:

　　def knapsack(items, maxWeight):

? 　　? items.sort(key=lambda x: x[1]/x[0], reverse=True)

?　　? ?weight = 0

　　? ? value = 0

?　　? ?for item in items:

? ?　　? ? ?if weight + item[0] <= maxWeight:

? ? 　　? ? ? ? weight += item[0]

? ? ?　　? ? ? ?value += item[1]

? ?　　? ? ?else:

? ? ? ? 　　? ? remaining = maxWeight – weight

? ? ? 　　? ? ? value += remaining * (item[1]/item[0])

? ? ? 　　? ? ? break

? 　　? return value

　　items = [(2,3),(3,4),(4,5),(5,6)]

　　maxWeight = 5

　　print(knapsack(items, maxWeight))

這個算法的復(fù)雜度是O(n log n)。