贪心算法

贪心算法

贪心算法是从问题的初始状态出发,通过若干次的贪心选择而得到的最优值(或较优
值)的一种求解问题的策略,即贪心策略。

贪心算法的特点

  1. 贪心选择

所谓贪心选择是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,而后
的每一步都是当前看似最佳的选择,且这种选择只依赖于已做出的选择,不依赖于未做
出的选择。

2.最优子结构

执行算法时,每一次得到的结果虽然都是当前问题的最优解(即局部最优解),但只有
满足全局最优解包含局部最优解时,才能保证最终得到的结果是最优解。

几个简单的贪心案例

  1. 最优装载问题

给 n 个物体,第 i 个物体重量为 wi,选择尽量多的物体,使得总重量不超过 C。

2.部分背包问题

有 n 个物体,第 i 个物体的重量为 wi,价值为 vi,在总重量不超过 C 的情况下让总价值
尽量高。每一个物体可以只取走一部分,价值和重量按比例计算。

3.乘船问题

有 n 个人,第 i 个人重量为 wi。每艘船的载重量均为 C, 最多可乘两个人,求用最少的
船装载所有人的方案。


贪心算法的经典应用

1.选择不相交区间问题

给定 n 个开区间$[ai, bi)$, 选择尽量多个区间,使得这些区间两两没有公共点。

【思路点拨】

首先,按照结束时间 $b_1<=b_2<=…<=b_n$ 的顺序排序,依次考虑各个活动,如果没有
和已经选择的活动冲突,就选,否则就不选。

【正确性】

假设$ b_j<b_i $且$ [a_j, b_j) $、$ [a_i, b_i) $分别与之前的活动不冲突,当前选$[a_j, b_j)$,若$[a_j, b_j)$与$[ai, bi)$
不冲突,这还可以选择$[a_i, b_i)$,答案个数加一;若$[a_j, b_j)$与$[a_i, b_i)$冲突,因为$ b_j<b_i$, 所以
$[a_j, b_j)$对以后的影响更小。

【例】活动安排

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇