算法-贪心算法简单介绍

下面是贪心算法视频课的导学内容.

1. 什么是贪心算法?

简单来说, 我们称以局部最优进而使得全局最优的一种思想实现出来的算法为贪心算法.
其过程, 往往分为:

1. 把解决问题分为若干部分
2. 解决每一步的时候, 都选择当前看起来"最优"的选择
3. “希望” 得到全局最优解

下面来解释两个引号词
“最优”: 上面说的意思是当前看来最优, 而不是从整体的角度看起来最优
“希望”: 意思是按这种思想去处理题目, 有可能会导致最后结果不是最优, 有可能从全局来看是最优结果的意思

2. 贪心算法简单的三个例子:

1. 找零问题

情景: 现在你有50块钱, 买了4块钱的东西, 卖家想要用最少的张数找你零钱.

此时可以试试贪心算法.

应该找你的钱数:

        50 - 4 = 46

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张20的

        46 - 20 = 26 此时还需要找你26元

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张20的

        26 - 20 = 6 此时还需要找你6元

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张5元的

        6 - 5 = 1 此时还需要找你1元

按照贪心策略, 此时应该找你一张最大面额的, 因此是给你一张1元的

        1 - 1 = 0 此时还需要找你0元

此时找钱结束

其过程如下:

2. 最小路径和问题

起点在(0, 0)位置, 规定只能左右上下移动, 在这其中会路过许多方块. 每次路过方块需要加上对应的"路径值", 问如何才能到达目的地同时求和为最小?

按照贪心思想, 过程如下:

3. 背包问题

最大背包容量为: 8单位, 如何放一些物品, 使得该背包拿到的总价值最高?

假设我们按照V去贪心: ③ * 8 -> 总价值是: 1 * 8 = 8

假设我们按照W去贪心: ① * 1 + ③ * 3 -> 总价值是: 10 + 1 * 3 = 13

假设我们按照W/V去贪心: ① * 1 + ③ * 3 -> 总价值是: 10 + 1 * 3 = 13

3. 贪心算法的特点

1. 贪心算法没有标准和模板, 贪心算法只是一种思想

2. 贪心算法需要证明其对错, 对的需要其证明他是对的, 错的需要证明, 或者举反例

对于证明这块来说,

2-1 显然找零问题是对的, 证明如下:

2-2 最小路径和问题 和 背包问题都是错误的, 证明如下(举反例):

4. 贪心算法学习的方式?

1. 遇到不会的很正常, 看多了解析就"可能"会了.
2. 注重证明. 比如"背包"和"路径和"问题贪心出来都不是最优解.

EOF.