|
EDA365欢迎您登录!
您需要 登录 才可以下载或查看,没有帐号?注册
x
《算法导论(第三版)》第十六章,贪心算法
3 s2 y7 _. x3 M: z9 s- ]16.1 活动选择问题/ V# J7 P. d @+ r% ]; k! b6 h
PS:为了代码方便,在相同思想下,将原始题目序列的首位加上0) A! S0 Z4 f2 G- W
- %该段代码的必备条件:序列以活动结束时间递增顺序排列
- %《算法导论》 第十六章 贪心算法 16.1活动选择问题
- clear;clc
- s=[0 1 3 0 5 3 5 6 8 8 2 12];%活动开始时间
- f=[0 4 5 6 7 9 9 10 11 12 14 16];%活动结束时间
- a=RECURSIVE_ACTIVITY_SELECTOR(s,f,1,length(s))%活动选择) g6 m, W+ N( f% h* X2 {5 ?
1 _5 ^' r" `/ M: d; y, z
8 E/ ?7 S: M) t. J3 B5 G& A( P5 T( P8 D, ^
( m& {, }& I4 r' B' s$ z* ?, g
) E% t0 D0 T/ x& `+ s; C5 d0 E; f递归活动选择器6 j% @/ c! q# q8 t* R" |
- function [a] = RECURSIVE_ACTIVITY_SELECTOR(s,f,k,n)
- %递归活动选择器
- %a 返回的序列结果
- m=k+1;
- while m<=n & s(m)<f(k)%检查是否兼容
- m=m+1;%若不兼容,进行下一位判断
- end
- if m<=n%整个序列
- a=[m RECURSIVE_ACTIVITY_SELECTOR(s,f,m,n)];%[当前最优值+在该条件下的后续最优值]
- else
- a=[];%所有搜索完毕,返回空值
- end
- end/ S6 p8 @ r M$ D& h
6 U; i- ?4 Z6 }8 k* P4 ~1 @
! A& Z- h' B/ ]
( u. C) [) h+ d h* ] |
|