贪心法与动态规划求解活动选择问题：时间复杂度和解的质量比较

设有 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 的变化曲线。比较计算结果，说明对该问题，贪心法是否一定会得到最优解，请根据实验结果说明理由。并写出代码内容：

贪心法求解近似解的思路如下：

将活动按照结束时间从早到晚进行排序。
选择第一个活动作为当前活动。
依次遍历剩余的活动，如果当前活动的结束时间早于下一个活动的开始时间，则选择下一个活动作为当前活动，并将其加入最终选择的活动集合中。
重复步骤 3，直到遍历完所有活动。

代码如下：

def greedy_activity_selection(start_time, finish_time):
    n = len(start_time)
    selected_activities = [0]
    current_activity = 0
    
    for i in range(1, n):
        if start_time[i] >= finish_time[current_activity]:
            selected_activities.append(i)
            current_activity = i
    
    return selected_activities

start_time = [1, 3, 0, 5, 8, 5]
finish_time = [2, 4, 6, 7, 9, 9]

print(greedy_activity_selection(start_time, finish_time))

对于最优解的求解，可以使用动态规划的方法。可以定义一个二维数组 dp，其中 dp[i][j] 表示在活动 i 到活动 j 中选择活动的最大数量。初始时，dp[i][j] = 0。然后，可以使用递推关系式来更新 dp 数组的值。递推关系式如下：

dp[i][j] = max(dp[i][j-1], dp[i][k] + dp[k+1][j] + 1)，其中 i ≤ k < j

最终，最优解为 dp[0][n-1]。

代码如下：

def optimal_activity_selection(start_time, finish_time):
    n = len(start_time)
    dp = [[0] * n for _ in range(n)]
    
    for gap in range(n):
        for i in range(n-gap):
            j = i + gap
            if i == j:
                dp[i][j] = 1
            elif start_time[j] >= finish_time[i]:
                dp[i][j] = max(dp[i][j-1], max(dp[i][k] + dp[k+1][j] + 1 for k in range(i, j)))
            else:
                dp[i][j] = dp[i][j-1]
    
    return dp[0][n-1]

start_time = [1, 3, 0, 5, 8, 5]
finish_time = [2, 4, 6, 7, 9, 9]

print(optimal_activity_selection(start_time, finish_time))

为了比较贪心法和最优解方法的执行时间随 n 的变化曲线，可以使用 Python 的 time 库来计算运行时间，并绘制图像。

代码如下：

import time
import matplotlib.pyplot as plt

def generate_activities(n):
    import random
    activities = []
    for _ in range(n):
        start_time = random.randint(0, 100)
        finish_time = start_time + random.randint(1, 10)
        activities.append((start_time, finish_time))
    return activities

def measure_time(n):
    activities = generate_activities(n)
    start_time = [activity[0] for activity in activities]
    finish_time = [activity[1] for activity in activities]
    
    # Measure time for greedy algorithm
    greedy_start = time.time()
    greedy_activity_selection(start_time, finish_time)
    greedy_end = time.time()
    
    # Measure time for optimal algorithm
    optimal_start = time.time()
    optimal_activity_selection(start_time, finish_time)
    optimal_end = time.time()
    
    return greedy_end - greedy_start, optimal_end - optimal_start

n_values = [8, 16, 32, 64, 128, 256]
greedy_times = []
optimal_times = []

for n in n_values:
    greedy_time, optimal_time = measure_time(n)
    greedy_times.append(greedy_time)
    optimal_times.append(optimal_time)

plt.plot(n_values, greedy_times, label='Greedy')
plt.plot(n_values, optimal_times, label='Optimal')
plt.xlabel('Number of activities')
plt.ylabel('Execution time (s)')
plt.legend()
plt.show()

根据实验结果，可以观察到贪心法的执行时间随着 n 的增加而线性增长，而最优解方法的执行时间随着 n 的增加而指数增长。这是因为贪心法只需要对所有活动进行一次排序，然后进行一次遍历，时间复杂度为 O(nlogn)，而最优解方法需要使用动态规划进行计算，时间复杂度为 O(n^3)。因此，贪心法在这个问题上可能无法得到最优解，但可以在较短的时间内给出一个近似解。