贪心算法

type
status
date
slug
summary
tags
category
icon
password
类别
内容

概念

贪心算法就是不断选择在当前看来是最好的选择，做出的选择只是在某种意义上的局部最优解
贪心算法不能对所有问题都得到整体最优解，但也是最优解的相似解

特性与选择

  1. 最优子结构性质：一个问题的最优解包含其子问题的最优解
  1. 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优解的选择得到
贪心算法和动态规划算法的异同
  1. 同：都具备最优子结构性质
  1. 异：
    1. 动态规划算法通常以自底向上的方式解决各子问题
    2. 贪心算法通常以自上向下的方式解决各子问题

贪心算法步骤

  1. 从某一起点触发
  1. 在每一个解决问题的步骤中，根据局部最优策略，得到一部分解，缩小问题规模
  1. 将所有解综合起来
高效和简洁的代码是贪心算法最大的优点

经典问题

翻硬币
找零
旅行家的预算
买股票的最佳时期I
买股票的最佳时期II
哈夫曼编码
最小生成树
单源最短路径—Dijkstra算法
 
数据结构回溯算法