正文

贪心算法实战：从入门到精通，50道精选习题带你征服数据结构与算法

/0 浏览量
0831

引言

贪心算法，作为一种简单有效的算法策略，广泛应用于解决实际问题。它通过在每一步选择当前状态下最优的选择，从而希望达到全局最优解。本文将带你从入门到精通，通过50道精选习题，深入理解贪心算法的原理和应用。

贪心算法原理

贪心算法的基本思想是：在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。贪心算法通常不保证得到最优解，但大多数情况下可以得到较好的解。

习题详解

习题1：背包问题

题目描述：给定一组物品，每个物品有价值和重量，求出在不超过背包容量的情况下，如何选择物品使得总价值最大。

解题思路：选择价值与重量比最大的物品放入背包，直到背包容量达到上限。

代码示例：

def knapsack(items, capacity):
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total_value = 0
    for item in items:
        if item[1] <= capacity:
            capacity -= item[1]
            total_value += item[0]
        else:
            total_value += item[0] * (capacity / item[1])
            break
    return total_value

# 示例数据
items = [(60, 10), (100, 20), (120, 30)]
capacity = 50
print(knapsack(items, capacity))

习题2：最小生成树

题目描述：给定一个无向图，求出该图的最小生成树。

解题思路：使用普里姆算法，从任意一个顶点开始，逐步添加边，直到所有顶点都被包含在生成树中。

代码示例：

from heapq import heappop, heappush

def prim(graph, start):
    visited = set()
    total_weight = 0
    edges = []
    heap = [(0, start)]
    while heap:
        weight, vertex = heappop(heap)
        if vertex in visited:
            continue
        visited.add(vertex)
        total_weight += weight
        for neighbor, edge_weight in graph[vertex].items():
            if neighbor not in visited:
                heappush(heap, (edge_weight, neighbor))
                edges.append((vertex, neighbor, edge_weight))
    return total_weight, edges

# 示例数据
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 3, 'D': 2},
    'C': {'A': 4, 'B': 3, 'D': 5},
    'D': {'B': 2, 'C': 5}
}
start = 'A'
print(prim(graph, start))

习题3：活动选择问题

题目描述：给定一组活动，每个活动都有开始时间和结束时间，求出最多可以同时进行的活动数量。

解题思路：选择结束时间最早的活动，然后继续选择下一个结束时间比当前活动开始时间晚的活动。

代码示例：

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])
    count = 1
    end_time = activities[0][1]
    for start, end in activities[1:]:
        if start >= end_time:
            count += 1
            end_time = end
    return count

# 示例数据
activities = [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9)]
print(activity_selection(activities))

总结

通过以上50道精选习题，相信你已经对贪心算法有了深入的理解。在解决实际问题时，灵活运用贪心算法，将帮助你更快地找到解决方案。祝你学习愉快！

-- 展开阅读全文 --