c语言算法设计策略--1贪心法


一、贪心法的思想

例:假如有一个人手上有四种面值的硬币,三角、一角五分、五分、二角,此时我们需要找零6角五分时,如何才能使找零的个数最少?
这时,我们会不加思索的找出2个三角一个五分的硬币。
这种找零的方式;
1 选出一个面值不超过六角五分的最大硬币,即三角
2 我们从六角五分中减去三角,剩余三角五分,然后我们再从硬币里面找出一个面值不大于三角五分的硬币,依次寻找下去,直到找零结束。
我们把这种找零的方式,称之为贪心法。


上述找零的算法利用的硬币的特殊性。
如果上述找零1角五分 硬币种类为 一分 五分 一角一分三种。如果我们采用上述的贪心法,那么得到的结果是一个一角一分 和四个一分 总共五个硬币,同我们直接找3个五分硬币相比,明显不是最优结果。

贪心法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。



二、贪心法的基本要素

使用贪心法需要具有两个重要的性质: 最优子结构性质和贪心选择性质
2.1 最优子结构性质
当一个问题的最优解一定包含其子问题的最优解时,称此问题具有最优子结构性质。

2.2 贪心选择性质
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得,其中每次所作的选择可以依赖于以前的选择,但不依赖于将来所做的选择。贪心选择性质保证了问题存在从贪心选择开始的最优解。


三、贪心法的算法设计模式

function decimal[] zhaoLin(decimal LingQian,decimal[] n)
  {
     decimal[] t; 
     for(i=0;i < n.length;i++){
         if(n[i] < = LingQian){  //采用贪心算法进行比对
           t.push(n[i]);       //合并最优解
           LingQian -=n[i];
        }
     }
    return t;
 }


四、贪心法举例说明

4.1 问题描述
在漆黑的夜里,N位旅行者来到一座桥,如果过这座桥,必须借助手电筒,否则的话,无法过桥,但是这时,大家只有一把手电筒,而桥每次只能通过两个人
如果单独过桥的话,N位旅行者所需时间已知;而如果两人同时过桥,所需时间为两人之中比较慢的一个人的过桥时间,现在我们需要设计一种最快的过桥方案
4.2 问题分析
每次过桥只能两个人一起通过,并且还需要有人将手电筒送过来,则只有当每次有人过桥后,将手电筒送过来所花费的时间最少,才能保证总时间最少,设N个人每个人过桥的花费时间为
t[0...N-1],然后将N个人过桥所需时间从小到大依次排序。
产生以下两种方案:
4.2.1
速度最快的人t[0] 和速度次快的人t[1] 过桥,然后速度最快的人将手电筒送来,再由速度次慢的人t[N-2] 和t[N-1] 依次过桥,再由t[1]将手电筒送回,依次循环过桥
4.2.2
速度最快的人t[0]和速度最慢的人过桥t[N-1],然后由t[0]将手电筒送回,再由速度最快的人和速度次慢的人一起过桥,再由速度最快的人将手电筒送回,依次循环过桥

4.2.1 过桥时间 t[0]+2*t[1]+t[N-1]
4.2.2 过桥时间 2*t[0]+t[N-2]+t[N-1]
如果4.2.1 过桥时间比4.2.2过桥时间短,那么就应该存在以下关系
t[0]+2*t[1]+t[N-1] < 2*t[0]+t[N-2]+t[N-1] //简写 2*t[1] 4.3 算法描述

     void fun(int n,int t[])
       {
        int first= 0;
        int last = n-1;
        int sum=0;
        while(last >= 2){
          if(last >= 3){
            if(t[last-1]+t[first] > 2*t[first+1]){
                sum += t[last]+t[first]+t[first+1]*2;
              }else
              {
                sum += t[first]*2+t[last-1]+t[last];
              }
              last =last -2;
          }else if(last ==2)
               sum +=t[first]+t[last];
       }
	sum +=t[first+1];
       }