《算法导论(第三版)》第十六章，贪心算法

Zedd

《算法导论(第三版)》第十六章，贪心算法
16.1 活动选择问题
% ~/ A$ {; ]- P* p( T  y2 e3 T. u2 C: P, OPS：为了代码方便，在相同思想下，将原始题目序列的首位加上0
4 I" R) }. m6 j: K9 Z1 A5 K

• %该段代码的必备条件：序列以活动结束时间递增顺序排列
• %《算法导论》 第十六章 贪心算法 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))%活动选择
  

1 ]: _8 J0 `1 v8 A9 k2 S* n
) s$ _8 z, J  e2 I( n$ C& C

: T' X7 s" S* ~1 D( f; D
# m. E' p4 D( }递归活动选择器
& P; |# y, N6 z. _4 Y5 Y

• 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
  

% L7 b0 @  T1 O9 U; W8 t/ J
+ k8 b& D' _1 ^: G1 M3 L7 s

relchhiclty

看看。

wu68aq

看一下。