贪心算法与动态规划算法在活动选择问题中的比较

import random
import time
import matplotlib.pyplot as plt


def generate_activities(n):
    '生成n个活动，每个活动的开始时间和结束时间随机生成。'
    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):
    '贪心算法选择活动。首先按照活动的结束时间进行排序，然后从第一个活动开始，选择结束时间最早且与前一个活动不重叠的活动，直到所有活动都被选择。'
    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):
    '动态规划算法选择活动。首先按照活动的结束时间进行排序，然后使用动态规划算法求解最长不重叠子序列的长度。最后根据最长不重叠子序列的长度和活动的结束时间，逆序选择活动。'
    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, 256]
    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')
    plt.legend()
    plt.show()


compare_execution_time()

通过比较执行时间，可以看出动态规划算法的执行时间随着活动数量的增加而增加，而贪心算法的执行时间相对较稳定。这是因为动态规划算法需要计算最长不重叠子序列的长度，时间复杂度为O(n^2)，而贪心算法只需要进行一次排序和一次遍历，时间复杂度为O(nlogn)。因此，在解决活动选择问题时，如果活动数量较大，可以选择贪心算法来获得更高的效率。