贪心算法几个经典例子python

贪心算法（Greedy Algorithm）是一种基本的算法思想。贪心算法的基本思路是在每一步选择中都采取在当前状态下最好或最优（局部最优解）的选择，从而希望到达全局最优解。贪心算法与动态规划算法不同的是，它不能回退。

在算法中，贪心策略通常建立在某种启发式规则上，由这样的启发式规则选择出的贪心策略通常不是全局最优策略，但能产生足够好的近似算法近似解。

下面我们来看几个常见的贪心算法例子：

1.最小生成树问题

在一个连通无向图中，每两个顶点之间都有一条边，并且每条边都有一个权值。现在需要构造一个生成树，它包含了所有的顶点，并且总权值最小。这就是一个最小生成树的问题。贪心算法主要采用有序连边贪心策略来解决最小生成树问题的。

Python实现最小生成树算法

```

def prim(graph):

"""

Implementation of Prim's algorithm for finding the minimum spanning tree

of an undirected graph.

"""

visited = {0}

heap = [(weight, 0, neig) for neig, weight in graph[0].items()]

heapq.heapify(heap)

total_weight = 0

while heap:

weight, frm, to = heapq.heappop(heap)

if to not in visited:

visited.add(to)

total_weight += weight

for neig, weight in graph[to].items():

if neig not in visited:

heapq.heappush(heap, (weight, to, neig))

return total_weight

```

2.活动选择问题

假定有一个贪心策略，总是选择活动中最早结束的。考虑证明该贪心策略的正确性。设已知最优策略S上活动按结束时间排序的第一个活动为a，而贪心策略选择的第一个活动为b。因为b和a结束时间相同，所以贪心策略也选择了a之外的某些活动。假设最优策略S在选择a之后，剩余的活动为S'，而贪心策略在选择b之后，剩余的活动为G'，则令最优策略S'与贪心策略G'在一起构成集合T。如果该集合中的某个元素不是活动，而是一个时间区间，那么把包含它的一个活动添加进来应该不增加总数，也不会产生冲突。

Python实现活动选择问题

```

def getActivityMax(activityList):

"""

:type activityList: List[Tuple[int,int]]

:rtype: int

"""

# sort activities by finishing time

activityList = sorted(activityList, key=lambda x: x[1])

activityCount = 0

lastActivityEnd = -1

for activity in activityList:

if activity[0] >= lastActivityEnd:

lastActivityEnd = activity[1]

activityCount += 1

return activityCount

```

3.背包问题

背包问题是另一个常见的贪心算法问题。 假设您是一个小偷，您有一个背包，它可以容纳一定的重量，您需要从商店中拿走一些物品，以获得最大的价值但是有一个重量限制，您需要在不超过容量的情况下获得最大价值。

Python实现背包问题算法

```

def knapSack(W, wt, val, n):

"""

:type W: int

:type wt: List[int]

:type val: List[int]

:type n: int

:rtype: int

"""

if n == 0 or W == 0:

return 0

# If the weight of the nth item is more than capacity W then this

# item cannot be included in the optimal solution

if wt[n-1] > W:

return knapSack(W, wt, val, n-1)

# return the maximum of two cases:

# (1) nth item included

# (2) not included

else:

return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),

knapSack(W, wt, val, n-1))

```

综上所述，贪心算法是解决各种问题非常有效的算法之一。虽然它不能保证得到全局最优解，但却可以得到非常接近最优解的近似解。除了上述几个例子，还有很多其他问题可以使用贪心算法来解决。