算法基本思想-贪心算法

贪心算法指的是，不管全局，只管优化当前局部的最优化，从而去实现全局最优. 但是注意并不是每次都可以达到全局最优，

基本思路

• 建立数学模型来描述问题
• 把求解的问题分成若干个子问题
• 对每个子问题求解，得到子问题的局部最优解
• 把子问题的解局部最优解合成原来问题的一个解

存在的问题

• 不能保证求得的最后解是最佳的
• 不能用来求最大值或最小值的问题
• 只能求满足某些约束条件的可行解的范围

贪心算法适用的问题

局部最优解能够实现全局最优。

例子

一个经典的贪心算法的小例子：

存在一个背包，一堆石头 背包只能装50kg的东西，要求装最高价值的方法;

石头价格和重量如图

如果采取优先往背包里塞最值钱的方案：

蓝石+黑石+xx石头 获得 350元

采取优先更重的

蓝+白+xx 获得 260元

根据代码获得性价比：

int [] zhonglaing={22,13,15,12,17,4};
          int [] jiazhi={120,40,30,200,110,30};
          double [] zuiyou=new double[6];
          for (int i=0;i<=zhonglaing.length-1;i++){
              zuiyou[i]=new BigDecimal((float)jiazhi[i]/zhonglaing[i]).setScale(10, BigDecimal.ROUND_HALF_UP).doubleValue();
          }
          for (double a:zuiyou) {
              System.out.println(a);
          }

优先放置性价比高的：黑+xx+白+红 12+4+17+13=46kg 得到390元

也就是当前利益最大话的方法，这种策略就是贪心