|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
《算法导论(第三版)》第十六章，贪心算法& |1 m3 d0 E, j: o1 r% A" ^* G- {
16.1 活动选择问题
6 M) Z) P* X- ?/ l4 L2 F, ^8 [PS：为了代码方便，在相同思想下，将原始题目序列的首位加上0
! l3 e) n. r& P* p4 P8 M. X3 U$ o- %该段代码的必备条件：序列以活动结束时间递增顺序排列
- %《算法导论》 第十六章 贪心算法 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))%活动选择, D9 P" B5 [9 [$ D
, l- M; v: {- I3 f: m' e( Z0 P
* W) c% p! z- Q3 V3 o- p
- X2 |( Q$ H8 O8 m) G3 M- W
9 f: A8 z. @3 X% _0 }2 p4 \: {' W) u9 P
递归活动选择器1 l+ V# J3 S9 z
- 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
- end3 B8 Y) e/ O' n& a; q
# a5 L; v" d n P- @0 k3 i- ]- k7 [0 U' @. o6 H
L. i$ x' h; f7 j; m- \3 E1 M |
|
/1 
发表于 2020-3-9 11:13
收藏
淘帖
支持！
反对！