Python实现活动选择问题的贪心算法与动态规划算法及性能比较

import random
import time
import matplotlib.pyplot as plt


def generate_activities(n):
    '''
    生成n个活动的起止时间

    Args:
        n: 活动数量

    Returns:
        一个列表，包含n个活动的起止时间，例如[(0, 1), (3, 5), (2, 7)]
    '''
    activities = []
    for i in range(n):
        start_time = random.randint(0, 100)
        end_time = start_time + random.randint(1, 10)
        activities.append((start_time, end_time))
    return activities


def greedy_activity_selection(activities):
    '''
    使用贪心算法求解活动选择问题

    Args:
        activities: 一个列表，包含活动的起止时间

    Returns:
        一个列表，包含被选择的活动的起止时间
    '''
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected_activities = []
    current_end_time = 0
    for activity in activities:
        if activity[0] >= current_end_time:
            selected_activities.append(activity)
            current_end_time = activity[1]
    return selected_activities


def dynamic_programming_activity_selection(activities):
    '''
    使用动态规划算法求解活动选择问题

    Args:
        activities: 一个列表，包含活动的起止时间

    Returns:
        一个列表，包含被选择的活动的起止时间
    '''
    n = len(activities)
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if activities[i][0] >= activities[j][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    max_activities = max(dp)
    selected_activities = []
    current_end_time = float('-inf')
    for i in range(n - 1, -1, -1):
        if dp[i] == max_activities and activities[i][1] >= current_end_time:
            selected_activities.append(activities[i])
            current_end_time = activities[i][0]
            max_activities -= 1
    return selected_activities[::-1]


def compare_execution_time():
    '''
    比较贪心算法和动态规划算法的执行时间
    '''
    n_values = [8, 16, 32, 64, 128]
    greedy_times = []
    dp_times = []
    for n in n_values:
        activities = generate_activities(n)

        start_time = time.time()
        greedy_activity_selection(activities)
        end_time = time.time()
        greedy_times.append(end_time - start_time)

        start_time = time.time()
        dynamic_programming_activity_selection(activities)
        end_time = time.time()
        dp_times.append(end_time - start_time)

    plt.plot(n_values, greedy_times, label='Greedy')
    plt.plot(n_values, dp_times, label='Dynamic Programming')
    plt.xlabel('Number of activities')
    plt.ylabel('Execution time (s)')
    plt.legend()
    plt.title('Execution Time Comparison: Greedy vs. Dynamic Programming')
    plt.show()


compare_execution_time()

代码说明

generate_activities(n): 该函数随机生成 n 个活动的起止时间，用于测试算法性能。
greedy_activity_selection(activities): 该函数实现了贪心算法，按照结束时间对活动进行排序，并选择结束时间最早的活动，直到没有活动可以再选择为止。
dynamic_programming_activity_selection(activities): 该函数实现了动态规划算法，使用一个 dp 数组记录每个活动最多可以选择多少个活动，最终回溯得到选择结果。
compare_execution_time(): 该函数比较了两种算法的执行时间，并使用 matplotlib 库绘制了折线图，直观地展示了两种算法的性能差异。

优化说明

在代码中添加了详细的注释，解释了每个函数的作用和实现细节，提高了代码的可读性和可维护性。
在绘图时，添加了标题、坐标轴标签和图例，使图形更加美观易懂。
将代码块使用 Markdown 语法进行格式化，方便用户阅读和复制。
将双引号改为单引号，符合 Python 代码规范。

总结

本文详细介绍了使用 Python 实现贪心算法和动态规划算法解决活动选择问题的方法，并对两种算法的性能进行了比较。通过本文，读者可以了解到两种算法的实现细节和性能差异，以及如何使用 Python 进行算法设计和性能分析。