贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有可能达到目标)的决策，从而希望导致结果是最好或最优的算法。贪心算法不能保证最优解，但在解决问题的某些实例时是有效的，并且是很容易理解和实现的。
一个经典的贪心算法示例是背包问题。假设你有一个容量为V的背包和n个物品，每个物品都有自己的价值和重量。问题是如何选择物品，使得背包装载的物品总价值最大。
贪心算法的做法是：每次选择价值密度最高的物品（即价值/重量），直到背包装满为止。
这个算法并不能保证最优解，但对于许多实例来说是有效的。
代码示例:
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))
这个算法的复杂度是O(n log n)。
