算法设计分析之贪心算法

贪心算法,是一种“只顾眼前”的价值观。远古的人会有这样的人生态度,我只关注每天能吃饱,就可以活下去。在几百万年前未尝不是一种好算法。

  1. 贪心算法的条件
      贪心算法需要满足无后效性。什么是有后效性呢?我当前这一步会给整个问题的情况带来改变。比如有一个路径问题,规定了走过的路不能再走,那这就是一个有后效性的问题。
      贪心算法也不适应那些活动收益不同的问题。比如背包问题:假设现在有几样价值不同,体积不同的东西需要装进容积为F的背包里,要求装入的总价值最大。用贪心算法来解,不能保证得到最优解。
    1. 贪心策略1:先装价值最大的东西。F=40,a(20,30),b(18,20),c(19,20)“前者价值,后者为体积”,这个情况贪心算法会选第一个a,但显然更好的选择是b&c,
    2. 贪心策略2:先装最小的。F=40,a(10,15),b(10,20),c(35,20).贪心算法会选a&b,但是显然b&c更好
    3. 贪心策略3:优先选择单位价值最大的。F = 40,a(10,10),b(20,10),c(35,40),贪心算法会选a(1)&b(2),但是c(0.825)是更好的选择。
      (当然上面的例子有点为难贪心算法的感觉,但是现实世界里就是这样,不会因为你的算法而改变问题来适应你)
  2. 贪心算法的应用
    1. 最优前缀码的构造。
      (未完待续)
    2. 在构造最优前缀码时,出现频率最小的字符可以不在最底层。频率比它大的字符可以在比它低的底层。

相关推荐