跳到主要内容

贪心算法与动态规划对比

在算法设计中，贪心算法（Greedy Algorithm）和动态规划（Dynamic Programming）是两种常见的优化策略。它们都用于解决最优化问题，但在思想、实现和应用场景上有显著的区别。本文将通过逐步讲解和实际案例，帮助你理解这两种算法的核心思想及其适用场景。

1. 贪心算法简介​

贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致全局最优解的算法。贪心算法的核心思想是“局部最优解导致全局最优解”。它通常适用于问题具有贪心选择性质和最优子结构性质的情况。

提示

贪心算法的关键在于每一步都做出当前最优的选择，而不考虑未来的影响。

贪心算法的特点​

  • 局部最优：每一步都选择当前最优解。
  • 无回溯：一旦做出选择，就不会再改变。
  • 高效：通常时间复杂度较低。

贪心算法的示例：找零问题​

假设我们需要用最少数量的硬币凑出某个金额。假设硬币面值为 [1, 5, 10, 25]，目标是凑出 36 美分。

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

coins = [1, 5, 10, 25]
amount = 36
print(coin_change(coins, amount))  # 输出: [25, 10, 1]

输入: coins = [1, 5, 10, 25], amount = 36
输出: [25, 10, 1]

2. 动态规划简介​

动态规划是一种通过将问题分解为子问题，并存储子问题的解来避免重复计算的算法。它适用于具有重叠子问题和最优子结构性质的问题。动态规划通常通过填表或递归的方式实现。

提示

动态规划的核心思想是“记住已经计算过的结果”，从而避免重复计算。

动态规划的特点​

  • 全局最优：通过子问题的解推导出全局最优解。
  • 存储中间结果：通常使用表格或数组存储子问题的解。
  • 时间复杂度较高：通常比贪心算法更复杂。

动态规划的示例：背包问题​

假设我们有一个背包，容量为 W，以及一些物品，每个物品有重量 w[i] 和价值 v[i]。目标是选择物品放入背包，使得总价值最大。

def knapsack(W, wt, val, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][W]

W = 50
wt = [10, 20, 30]
val = [60, 100, 120]
n = len(wt)
print(knapsack(W, wt, val, n))  # 输出: 220

输入: W = 50, wt = [10, 20, 30], val = [60, 100, 120]
输出: 220

3. 贪心算法与动态规划的对比​

核心思想​

  • 贪心算法：每一步都选择当前最优解，不考虑未来的影响。
  • 动态规划：通过子问题的解推导出全局最优解，存储中间结果以避免重复计算。

适用场景​

  • 贪心算法：适用于问题具有贪心选择性质和最优子结构性质的情况，例如找零问题、活动选择问题。
  • 动态规划：适用于问题具有重叠子问题和最优子结构性质的情况，例如背包问题、最长公共子序列问题。

时间复杂度​

  • 贪心算法：通常时间复杂度较低，例如 O(n) 或 O(n log n)。
  • 动态规划：通常时间复杂度较高，例如 O(n^2) 或 O(n * W)。

空间复杂度​

  • 贪心算法：通常空间复杂度较低，例如 O(1) 或 O(n)。
  • 动态规划：通常空间复杂度较高，例如 O(n * W)。

4. 实际案例​

案例 1：活动选择问题（贪心算法）​

假设我们有一组活动，每个活动有开始时间和结束时间。目标是选择尽可能多的互不重叠的活动。

def activity_selection(start, finish):
    n = len(start)
    selected = []
    i = 0
    selected.append(i)
    for j in range(1, n):
        if start[j] >= finish[i]:
            selected.append(j)
            i = j
    return selected

start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, finish))  # 输出: [0, 1, 3, 4]

输入: start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9]
输出: [0, 1, 3, 4]

案例 2：最长公共子序列问题（动态规划）​

给定两个字符串，找到它们的最长公共子序列。

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

X = "ABCBDAB"
Y = "BDCAB"
print(lcs(X, Y))  # 输出: 4

输入: X = "ABCBDAB", Y = "BDCAB"
输出: 4

5. 总结​

贪心算法和动态规划是解决最优化问题的两种重要方法。贪心算法通过局部最优解推导全局最优解，适用于问题具有贪心选择性质的情况；动态规划通过存储子问题的解避免重复计算，适用于问题具有重叠子问题和最优子结构性质的情况。

警告

贪心算法并不总是能得到全局最优解，因此在选择算法时需要仔细分析问题的性质。

6. 附加资源与练习​

附加资源​

练习​

  1. 实现一个贪心算法解决“最小生成树”问题。
  2. 实现一个动态规划解决“编辑距离”问题。
  3. 比较贪心算法和动态规划在“背包问题”中的表现。

希望本文能帮助你更好地理解贪心算法与动态规划的区别与联系！如果你有任何问题，欢迎在评论区留言。