正文

掌握贪心算法，轻松破解经典习题攻略

/0 浏览量
0919

在算法领域，贪心算法是一种简单而有效的求解问题的方法。它通过在每一步选择当前状态下最优解的策略来构造问题的解。贪心算法虽然不能保证找到全局最优解，但在很多情况下可以找到近似最优解，且效率较高。本文将介绍贪心算法的基本概念，并通过一些经典习题来帮助你更好地理解和掌握这一算法。

贪心算法的基本概念

贪心算法的核心思想是：在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法的特点如下：

  1. 局部最优解：每一步都选择当前局部最优解。
  2. 不可逆性：一旦做出了选择，就不能再更改。
  3. 可能不唯一：对于同一个问题，可能存在多个局部最优解。

经典习题解析

下面，我们将通过几个经典习题来讲解贪心算法的应用。

习题1：背包问题

题目描述：给定一个背包，其容量为C，有N件物品，每件物品有价值和重量，问如何选择物品放入背包，使得背包的总价值最大。

贪心算法解法：

  1. 计算每件物品的价值密度（价值/重量）。
  2. 按照价值密度从大到小排序。
  3. 从价值密度最高的物品开始，逐个放入背包，直到背包满为止。

示例代码：

def knapsack(values, weights, capacity):
    n = len(values)
    item_density = [(value / weight, index) for index, (value, weight) in enumerate(zip(values, weights))]
    item_density.sort(reverse=True, key=lambda x: x[0])
    total_value = 0
    for density, index in item_density:
        if capacity >= weights[index]:
            capacity -= weights[index]
            total_value += values[index]
        else:
            break
    return total_value

# 示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(knapsack(values, weights, capacity))  # 输出：220

习题2：活动选择问题

题目描述：给定N个活动，每个活动有开始时间和结束时间，问如何选择活动，使得选中的活动互不重叠，且数量最多。

贪心算法解法：

  1. 按照活动结束时间进行排序。
  2. 从第一个活动开始，选择当前活动中结束时间最早的，然后从下一个活动开始重复步骤2。

示例代码：

def activity_selection(start_times, end_times):
    n = len(start_times)
    activities = [(start, end) for start, end in zip(start_times, end_times)]
    activities.sort(key=lambda x: x[1])
    max_activities = 1
    end_time = activities[0][1]
    for start, end in activities[1:]:
        if start >= end_time:
            max_activities += 1
            end_time = end
    return max_activities

# 示例
start_times = [1, 3, 0, 5, 8, 5]
end_times = [2, 4, 6, 7, 9, 9]
print(activity_selection(start_times, end_times))  # 输出：4

习题3：硬币找零问题

题目描述：给定硬币的面值和目标金额，问如何使用最少的硬币凑出目标金额。

贪心算法解法：

  1. 按照硬币面值进行排序。
  2. 从最大面值开始，尽可能多地使用该面值的硬币。
  3. 重复步骤2，直到目标金额为0。

示例代码：

def coin_change(coins, amount):
    coins.sort(reverse=True)
    total_coins = 0
    for coin in coins:
        if amount >= coin:
            total_coins += amount // coin
            amount %= coin
    return total_coins

# 示例
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出：4

总结

通过以上经典习题的讲解，相信你已经对贪心算法有了更深入的理解。贪心算法虽然不能保证找到全局最优解，但在很多情况下可以找到近似最优解，且效率较高。在实际应用中，我们需要根据问题的特点选择合适的贪心算法进行求解。希望本文对你有所帮助！

-- 展开阅读全文 --