11 贪心与动态规划的区别

在前一篇中，我们简单介绍了贪心算法的基础，理解了其基本原理及应用场景。本文将深入探讨贪心算法与动态规划的区别，以帮助大家更好地理解这两种算法的特性、适用情况和解决问题的思路。

基本概念回顾

贪心算法

贪心算法是一种通过每一步都选择当前状态下最优解的方式，达到全局最优的一种算法。它基于这样一个假设：局部最优解能够导致全局最优解，因此我们每次都选择当前看起来最好的选项。

动态规划

动态规划是一种将复杂问题分解为更简单子问题的方法，它通过存储之前的计算结果来避免重复计算。动态规划适用于那些可以通过子问题来构造最优解的问题，通常需要明确重叠子问题和最优子结构的特性。

贪心算法与动态规划的主要区别

1. 解的构造方式

• 贪心算法的构造是通过局部最优选择获取全局最优，而并不考虑以后的决策。

  示例：考虑活动选择问题，选择不重叠的活动。贪心策略是每次选择结束时间最早的活动，直到无法添加更多活动。

• 动态规划则考虑所有可能的选择，通过构造子问题的最优解逐步解决全局问题。

  示例：使用背包问题来说明，选择物品时需要仔细考虑每个物品的选择与否，并记录每一步的结果，由此建立出最终的最优解。

2. 适用问题的类型

• 贪心算法通常适用无后效性的问题，即之后的决策不会影响当前的选择。

• 动态规划则适合重叠子问题和最优子结构的问题，在求解中需要保存之前的计算结果以便重复使用。

3. 复杂度与效率

• 贪心算法通常具有较低的时间复杂度，运行效率高，但并不是所有问题都能通过贪心算法得到最优解。

• 动态规划通常涉及到更多的计算，在时间复杂度上较高，但其系统化的结果保证了找到全局最优解。

具体案例分析

1. 贪心算法案例

活动选择问题：
假设我们有一系列活动，每个活动都有开始和结束时间，我们需要选择最多的互不冲突的活动。

活动列表：

• (1, 3)
• (2, 5)
• (4, 6)
• (6, 7)
• (5, 8)

贪心策略：

1. 首先将活动按结束时间排序。
2. 选择第一个活动，然后选择下一个结束时间在上一个选择的结束时间后的活动。

代码实现：

def activity_selection(activities):
    # 排序
    activities.sort(key=lambda x: x[1])
    
    selected_activities = []
    last_end_time = 0
    
    for start, end in activities:
        if start >= last_end_time:
            selected_activities.append((start, end))
            last_end_time = end
    
    return selected_activities

activities = [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8)]
print(activity_selection(activities))

2. 动态规划案例

0-1背包问题：
给定一个背包的最大承重以及一系列物品的价值和重量，求能放入背包的最大价值。

动态规划策略：

1. 通过状态转移方程建立表格来记录每种状态的最优解。
2. 根据物品的重量和价值决定是否包括该物品。

状态转移公式：
$$
dp[i][w] = \max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
$$

代码实现：

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

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W))

总结

在处理问题时，贪心算法和动态规划各有优劣。在做出选择时，建议先分析问题的特性，确认其是更趋向于贪心还是动态规划。通过本篇的学习希望能够加深大家对这两种算法的理解，为处理相关的算法问题打下更加坚实的基础。

在下一篇文章中，我们将展示一些经典的贪心算法实例，通过具体的例子来强化对贪心算法的理解与应用。