动态规划之活动选择加权问题

Question

活动选择问题(加权)：给定一系列活动ai，其对应的开始时间为si，结束时间为fi，每个活动还有一个对应的权值vi（价值），问题是需要找出若干个相容的活动，使得总的权值最大，这个怎么写，用python，急

Answer 1

对活动按照结束时间进行排序。
对于每个活动，考虑是否选择它：选择该活动时，可以选择的下一个活动必须在其结束时间之后开始，且选择该活动时的总价值为它的权值加上前面相容活动的最大权值；不选择该活动时，总价值为前面活动的最大权值。
通过动态规划表来保存这些最优子结构的解，最终找到最大值。
下面是使用Python实现的解决方案：

# 导入二分查找库
from bisect import bisect_right

# 活动选择函数
def weighted_activity_selection(activities):
    # 按照结束时间对活动进行排序
    activities.sort(key=lambda x: x[1])  # 根据结束时间排序
    n = len(activities)
    
    # 动态规划数组，dp[i] 表示在第i个活动之前能取得的最大价值
    dp = [0] * n
    
    # 记录每个活动能选择的前一个活动
    def find_last_non_conflict(i):
        # 使用二分查找找到最靠近且不冲突的活动
        lo, hi = 0, i - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if activities[mid][1] <= activities[i][0]:
                if activities[mid + 1][1] <= activities[i][0]:
                    lo = mid + 1
                else:
                    return mid
            else:
                hi = mid - 1
        return -1
    
    # 初始化第一个活动的价值
    dp[0] = activities[0][2]
    
    # 填充dp数组
    for i in range(1, n):
        # 包含当前活动的价值
        incl = activities[i][2]
        l = find_last_non_conflict(i)
        if l != -1:
            incl += dp[l]
        
        # 不包含当前活动的价值
        excl = dp[i - 1]
        
        # 当前的最大价值
        dp[i] = max(incl, excl)
    
    # 返回最大价值
    return dp[-1]

# 测试活动选择
# 每个活动表示为 (开始时间, 结束时间, 价值)
activities = [
    (1, 4, 5),   # 活动1: 开始时间1，结束时间4，价值5
    (3, 5, 1),   # 活动2: 开始时间3，结束时间5，价值1
    (0, 6, 8),   # 活动3: 开始时间0，结束时间6，价值8
    (4, 7, 4),   # 活动4: 开始时间4，结束时间7，价值4
    (3, 8, 6),   # 活动5: 开始时间3，结束时间8，价值6
    (5, 9, 2),   # 活动6: 开始时间5，结束时间9，价值2
    (6, 10, 10), # 活动7: 开始时间6，结束时间10，价值10
    (8, 11, 11), # 活动8: 开始时间8，结束时间11，价值11
]

输出最大价值

max_value = weighted_activity_selection(activities)
print("最大总价值为:", max_value)