- 收藏
- 点赞
- 分享
- 举报
贪心算法解读: 1.贪心算法建议通过一系列步骤来构造问题的解,每一步都对目前构造的部分做一个扩展,直到获得问题的完整解为止。 2.在每一步中,它“贪心”地选择最佳操作,并希望通过一系列局部的最优选择,能够产生一个整个问题的全局最优解 3.事实上,贪心算法不是对所有问题都能得到整体最优解,但许多问题他能产生整体最优解或整体最优的近似解。
贪心算法举例——找零钱 买东西时,售货员常常会计算最少需要找多少张零钱,以便简化工作流程。比如顾客购物需要48.5元,他交给售货员100元整,则售货员最少需要找三张零钞:50元一张,1元一张,5角一张。
算法分析:
贪心算法举例——石子合并问题
在操场上的四周摆放N堆石子,现要将石子有序的合并成一堆,规定每次只能选相邻的两堆合并,并将新的一堆石子记作为该次合并得分。已知每堆石子数量,请选择一种方案,使得N-1次合并得分的总和最小。
得到总分和=8+13+22=43
得到总分和=5+9+9+15+24=62
我们来看另外一种不用贪心法
这里我们得到总分的和是=6+7+11+13+24=61
这里大家可做思考
下面来给大家运用编程举例 贪心算法——活动安排问题
1.设有n个活动的集合S=(1,2....,n),其中每个活动都要求使用同一资源,如学校礼堂,而在同一时间内只有一个活动能使用该资源。 2.每个活动都有使用的起始时间b1和结束时间e1,如果bi>=ej或bj>=ej(即一个活动结束后另一个开始)则活动i与活动j相容。 3.活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。
贪心策略——选择结束时间尽量早的活动,以便腾出更多时间留给后续活动 不妨假设活动已安排好。我们来用编程实现该问题 1.在下列算法中,n为活动个数,数组b[]和e[]分别为活动开始和结束时间,假设活动已经按结束时间递增排列:e[1]<=e[2]<=...<=e[n] 2.数组A记录所有选择的活动,A[i]=1表示活动i被选中,A[i]=0表示活动i未被选中
GreedyActivitySelector(n,b[],e[],A[])
{
A[1]=1; //选中活动1
j=1; //记录最后选中的活动
for(i从2到n)
{
if(b[i]>=e[j]){
A[i]=1; //选中活动i
j=i //记录最后选中的活动
}
}
}
-
浏览量:3731次2021-07-02 14:29:37
-
浏览量:1032次2020-01-14 09:11:57
-
浏览量:1259次2020-05-06 09:55:45
-
浏览量:950次2023-01-21 10:13:45
-
浏览量:5064次2021-06-11 10:08:48
-
浏览量:3573次2021-05-25 16:44:59
-
浏览量:4222次2021-04-12 16:28:50
-
浏览量:3408次2019-12-23 11:03:59
-
浏览量:2417次2020-08-04 17:37:01
-
浏览量:4216次2021-07-20 13:48:35
-
浏览量:275次2023-04-17 16:22:11
-
浏览量:1246次2020-01-03 10:44:52
-
浏览量:361次2023-04-14 10:09:56
-
浏览量:3328次2022-03-09 09:00:20
-
浏览量:1991次2020-08-19 16:44:21
-
浏览量:196次2023-05-16 15:43:05
-
浏览量:7251次2020-12-08 14:09:20
-
浏览量:10921次2021-01-01 02:53:29
-
浏览量:1068次2019-09-06 17:19:50
1






举报类型
- 内容涉黄/赌/毒
- 内容侵权/抄袭
- 政治相关
- 涉嫌广告
- 侮辱谩骂
- 其他
详细说明