带权活动选择
Howard Yin 2020-12-27 14:41:04 数学OJ笔记算法
Description
给定n个活动,活动ai表示为一个三元组(si,fi,vi),其中si表示活动开始时间,fi表示活动的结束时间,vi表示活动的权重, si<fi。带权活动选择问题是选择一些活动,使得任意被选择的两个活动ai和aj执行时间互不相交,即区间[si,fi)与[sj,fj)互不重叠,并且被选择的活动的权重和最大。请设计一种方法求解带权活动选择问题。
Input
第一行输入M(M≤10)表示有M组数据。每组数据输入整数N(N≤10000), 接下来输入N个活动。
Output
输出M行正整数,第i行表示第i组数据的能够选择活动最大权值和。
# 解析
和01背包问题类似,使用动态规划方法。
首先将活动按结束时间顺序进行排序。定义从最早结束的活动到第i个结束的活动的最优排列方案为f(i),与结束时间早于s的活动集合的最优排列方案为为g(s)=f(j)(fj≤s),那么f(i)满足最优子结构特性:
f(i)=max{f(i−1),g(si)+vi}
显然,f(i)的重叠子问题集合为:
{f(i)∣1≤i≤n}
空间复杂度为o(n),每个子问题都只需要计算其之前的两个值,因此时间复杂度为O(n),再加上开始时的排序时间,时间复杂度为O(nlogn)