算法小专栏:贪心算法

栏目: 编程工具 · 发布时间: 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更好。


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

查看所有标签

猜你喜欢:

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

深入理解计算机系统(原书第2版)

深入理解计算机系统(原书第2版)

(美)Randal E.Bryant、David O'Hallaron / 龚奕利、雷迎春 / 机械工业出版社 / 2011-1-1 / 99.00元

本书从程序员的视角详细阐述计算机系统的本质概念,并展示这些概念如何实实在在地影响应用程序的正确性、性能和实用性。全书共12章,主要内容包括信息的表示和处理、程序的机器级表示、处理器体系结构、优化程序性能、存储器层次结构、链接、异常控制流、虚拟存储器、系统级I/O、网络编程、并发编程等。书中提供大量的例子和练习,并给出部分答案,有助于读者加深对正文所述概念和知识的理解。 本书的最大优点是为程序......一起来看看 《深入理解计算机系统(原书第2版)》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具