算法小专栏:贪心算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:贪心算法,又称“贪婪算法”。 在对问题求解时,总是做出在当前看来是最好的选择。(局部最优解) 也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的注:贪心算法是一种高性能算法,复杂度低,简单易用。 贪心算法求出来的结果不一定都是最优解。对于某些问题,它能求出最优解。而还有些问题,它能求出最优解的**“近似解”**。“大事化小,小事化了”。

贪心算法,又称“贪婪算法”。 在对问题求解时,总是做出在当前看来是最好的选择。(局部最优解) 也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的 局部最优解 。 贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的 近似解 。(来源360百科)

注:贪心算法是一种高性能算法,复杂度低,简单易用。 贪心算法求出来的结果不一定都是最优解。对于某些问题,它能求出最优解。而还有些问题,它能求出最优解的**“近似解”**。

二、算法思想

“大事化小,小事化了”。

  • 大事化小:一个较大的问题,通过找到与子问题的重叠,把复杂的问题划分为多个小问题;

  • 小事化了:从小问题找到决策的核心,确定一种局部最优解的策略。

  • 通过计算出局部的最优解,来推出全局的最优解或近似解。

伪代码如下:

从问题的某一初始解出发
    while (能朝给定总目标前进一步) 
        do
            选择当前最优解作为可行解的一个解元素;
    由所有解元素组合成问题的一个可行解。
复制代码

三、找零问题

这是一个求得 最优解 的贪心算法例子。

场景:一名收银员,需要找零 88 元。 怎么找零,所需要的纸/硬币的数量最少。

思路:依次找最大的纸币, 例如:找零88元, ¥88 = ¥50 + ¥20 + ¥10 + ¥5 + ¥1 * 3

# arr的每一位:分别对应100块、50块、20块、10块、5块、1块纸币。
arr = [0,0,0,0,0,0]

def change(money):
    while money >= 1:
        if money >= 100:
            money -= 100
            arr[0] += 1
        elif money >= 50:
            money -= 50
            arr[1] += 1
        elif money >= 20:
            money -= 20
            arr[2] += 1
        elif money >= 10:
            money -= 10
            arr[3] += 1
        elif money >= 5:
            money -= 5
            arr[4] += 1
        elif money >= 1:
            money -= 1
            arr[5] += 1

change(88)
print arr
复制代码

结果输出:

算法小专栏:贪心算法

四、0-1背包问题

这是一个求得最优解的 近似解 的贪心算法例子。 而如果要想求得最优解,就要用到DP策略。而动态规划将在 下篇 介绍。

场景:一个小偷去商场偷东西,在背包称重有限下,如何拿能使得获得收益越大?(每件商品只有一个,只能选择拿与不拿)

  • 贪心策略1:每次取当前能拿得下的 最值钱 的商品。
  • 贪心策略2:每次取当前重量 最轻 的商品。
  • 贪心策略3:每次取 性价比最高 的商品。(即 价格/重量 的值最大的商品)

接下来我们依次分析,并且找出不是最优解的反例。

贪心策略1:选取价值最大的商品。

反例: 背包最大重量 W = 4kg

商品 价格 重量
商品A 3000元 4kg
商品B 2000元 3kg
商品C 1500元 1kg

根据策略,首先选取商品A,接下来就无法再选取了,可是明明选取商品B、C更好。

贪心策略2:选取重量最轻的商品。

与策略1类似,举反例: 背包最大重量 W = 4kg

商品 价格 重量
商品A 3500元 4kg
商品B 2000元 3kg
商品C 1000元 1kg

根据策略,首先选取商品C,接下来选取商品B,可是明明选取A更好。


以上所述就是小编给大家介绍的《算法小专栏:贪心算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员的自我修养

程序员的自我修养

陈逸鹤 / 清华大学出版社 / 2017-5 / 49.00

程序员作为一个职业、也作为一个群体,正逐渐从幕后走向前台,并以他们自己的能力加速改变着世界,也改变着人们生活的方方面面。然而,对于程序员,特别是年轻程序员们来说,如何理解自己的职业与发展,如何看待自己的工作与生活,这些问题往往比那些摆在面前的技术难题更让他们难以解答。 这本书从一个成熟程序员、一名IT管理者的角度,以杂记的形式为大家分享关于国内程序员职业生涯、个人发展、编程中的实践与认知乃至......一起来看看 《程序员的自我修养》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

html转js在线工具
html转js在线工具

html转js在线工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具