贪心算法
贪心算法
贪心算法是从问题的初始状态出发,通过若干次的贪心选择而得到的最优值(或较优 值)的一种求解问题的策略,即贪心策略。
贪心算法的特点
贪心选择
所谓贪心选择是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,而后 的每一步都是当前看似最佳的选择,且这种选择只依赖于已做出的选择,不依赖于未做 出的选择。
2.最优子结构
执行算法时,每一次得到的结果虽然都是当前问题的最优解(即局部最优解),但只有 满足全局最优解包含局部最优解时,才能保证最终得到的结果是最优解。
几个简单的贪心案例
最优装载问题
给 n 个物体,第 i 个物体重量为 wi,选择尽量多的物体,使得总重量不超过 C。
2.部分背包问题
有 n 个物体,第 i 个物体的重量为 wi,价值为 vi,在总重量不超过 C 的情况下让总价值 尽量高。每一个物体可以只取走一部分,价值和重量按比例计算。
3.乘船问题
有 n 个人,第 i 个人重量为 wi。每艘船的载重量均为 C, 最多可乘两个人,求用最少的 船装载所有人的方案。
贪心算法的经典应用1.选择不相交区间问题
给定 n 个开区间$[a ...
上海市未来工程师大赛游记
Day 1这个鬼比赛只有一天,还分什么day1、day2
前序一早起床,倒腾了一下服务器,总算把Apache2 phpmyadmin什么的都安装好了,把wordpress也部署好了,便驱车前往南洋中学,还好有点关系,可以把车停在学校内部的地下停车场,不得不说,这个学校的地下空间利用的是挺充分的,停车场和每个楼都是相通的,佩服。
相遇从学校里面出来,外面成群成片的人都在玩手机、玩游戏走了不远就碰见一群骚货站在一起,其中不乏有哲学家——傅秋莱,还有我们的Van。 最迟到的是ZP背着很骚的包迟迟到了校门口。、
寻位校门终于开放,成群的人走进了大门,我们在幕布处拍了集体照便分别前往比赛区域了…
位置找了很久都没有找到,地下的食堂很大啊;
好不容易找到了部署好环境了,比赛而就开始了额。
编写刚开始不是很慌,悠悠哉哉地写着代码,到后来只有我没有做完,于是慌慌张张张地写完代码,选择了其中几个比较好实现的功能,随便乱写了一点,就过去答辩了。
答辩我们派出了Van进行答辩,Van精湛的吹牛逼技巧带领我们走向了胜利,然而,这个比赛的奖项到现在都没有出来
完了
二分常见模型
二分法常见模型
二分查找(基础)
二分答案(重点)
代替三分(*)
注:*为扩展内容
二分答案概念二分答案,就是二分枚举答案,由于进行二分,所以时间复杂度 O(二分次数*单次判定时间复杂度)。
二分答案与二分查找类似,即对有着单调性的答案进行二分,确定可能的答案后,配合贪心、DP 等其他算法检验这个答案是否合理,不断缩减范围,最终确定答案的方法。常见的检验算法如穷举、贪心、搜索、动态规划、图论、数据结构等,可以看到,二分答案问题很好地结合了其他算法知识,非常受命题者欢迎。答案的单调性大多数情况下可以转化为一个函数,其单调性证明多种多样,如下:
移动石头的个数越多,答案越大(NOIP2015跳石头)
前 i 天的条件一定比前 i + 1 天条件更容易(NOIP2012 借教室)
满足更少分配要求比满足更多的要求更容易(NOIP2010 关押罪犯)
满足更大最大值比满足更小最大值的要求更容易(NOIP2015 运输计划)
时间越长,越容易满足条件(NOIP2012 疫情控制)
可以解决的常见问题
求最大的最小值(NOIP2015跳石头)
求最小的最大值(NOIP2010 关押罪犯)。 ...







