|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
《算法导论(第三版)》第十六章，贪心算法
3 ?. q" |1 ?' O" E! i1 G4 t16.1 活动选择问题% |: t( n! r% {- P. X# t9 U
PS：为了代码方便，在相同思想下，将原始题目序列的首位加上00 h( b& p C1 ?# P, B
- %该段代码的必备条件：序列以活动结束时间递增顺序排列
- %《算法导论》 第十六章 贪心算法 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))%活动选择
2 P0 ?; u G+ w/ G# H
+ z) n8 H5 C+ r5 v. t
+ ^; |5 b# A* E5 X+ Z$ n$ j
1 N3 n/ n' u9 `* z
+ [/ B; p4 `: X2 D0 V; H
! s) Z$ U- o% s2 m7 @. s递归活动选择器0 n; ?% M1 w6 ^/ F$ p: n! k; s3 e" c
- 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/ B0 n% V- l# B D8 u% ^
% @& @6 e& V5 m ~. j
% |5 B3 {$ ^( F
+ |7 w6 R' b" Y- F
|
|
/1 
发表于 2020-3-9 11:13
收藏
淘帖
支持！
反对！