程序设计与问题求解——贪心算法实例解读
8207 打赏
1 2020-12-04 10:03:41

贪心算法解读: 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        //记录最后选中的活动
        }
    }
}
声明:本文内容由易百纳平台入驻作者撰写,文章观点仅代表作者本人,不代表易百纳立场。如有内容侵权或者其他问题,请联系本站进行删除。
评论
0个
时间排序
内容存在敏感词
    0 条记录 第 0 /
    相关专栏
    打赏作者
    易百纳技术社区
    1
    您的支持将鼓励我继续创作!
    打赏金额:
    ¥1 易百纳技术社区
    ¥5 易百纳技术社区
    ¥10 易百纳技术社区
    ¥50 易百纳技术社区
    ¥100 易百纳技术社区
    支付方式:
    微信支付
    支付宝支付
    易百纳技术社区 微信支付
    易百纳技术社区
    打赏成功!

    感谢您的打赏,如若您也想被打赏,可前往 发表专栏 哦~

    举报反馈

    举报类型

    • 内容涉黄/赌/毒
    • 内容侵权/抄袭
    • 政治相关
    • 涉嫌广告
    • 侮辱谩骂
    • 其他

    详细说明

    审核成功

    发布时间设置
    发布时间:
    是否关联周任务-专栏模块

    审核失败

    失败原因
    备注
    Loading...
    易百纳技术社区
    确定要删除此文章、专栏、评论吗?
    确定
    取消
    易百纳技术社区
    活动规则
    • 1.周任务为周期性任务,每周周一00:00刷新,上周完成的任务不会累计到本周,本周需要从头开始任务,当前任务完成后才可以完成下一个任务
    • 2.发布在平台的专栏需为原创技术专栏,且社区作为首次发布的平台,在其他平台发布需注明为转载
    • 3.周任务中的专栏需要达到一定质量才会被计入完成总数中。具体以平台审核为准,如有疑问,可联系社区客服(ebainacs)。
    • 4.专栏/资料的任务以审核通过的篇数为准,每个任务数量不做累计。
    • 5.任务完成后,现金奖励直接打款到微信账户EBC/收益将自动发放到个人账户,可前往“我的钱包”查看;其他奖励请联系客服兑换。
    易百纳技术社区
    升级提醒
    升级

    恭喜您的社区称号由 升级为 “社区游民”

    同时为了感谢您对社区的支持,我们将送出xxx礼品一份, 记得领取哦~

    升级提醒
    易百纳技术社区