|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
《算法导论(第三版)》第十六章，贪心算法
2 u9 ~) D0 a( S/ _$ b16.1 活动选择问题
6 a4 t+ \& `. S& _' b6 B# J% ]PS：为了代码方便，在相同思想下，将原始题目序列的首位加上0
( c" L* O/ m8 t7 U- %该段代码的必备条件：序列以活动结束时间递增顺序排列
- %《算法导论》 第十六章 贪心算法 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))%活动选择& a: Q$ M3 g4 M p% y- X
" B- j5 J$ l, @+ y4 ^" W1 [
& S6 u: J* C) f) p! Y9 p) Z& U% R; q+ s2 N: I5 U' a6 M/ i8 [
3 z( i! w- k2 k3 ?4 O. N$ x6 ~9 a1 p2 u
递归活动选择器
; J9 g! ]. c3 x! |8 t- 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
1 s: q1 V+ c& m8 ^
# ~! R m' f+ `+ c. V# j
, Z2 {0 h4 f2 V2 n2 b) j# a
, m" r8 s+ F$ a8 s+ x2 @2 E6 @
|
|
/1 
发表于 2020-3-9 11:13
收藏
淘帖
支持！
反对！