算法之贪心算法_贪心算法的研究现状和发展

贪心算法

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

贪心策略 ： 一般来说，适用于贪心策略求解的问题具有以下特点：贪心选择性质和最优子结构性质。
　　① 贪心选择性质：可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
　　② 最优子结构性质：原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推

贪心算法使用场景

1 当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大

2 我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据
3 贪心算法产生的结果是否是最优的。

动态规划、回溯法、贪心算法区别

三个算法解决问题的模型，都可以抽象成我们今天讲的那个多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽 象成多阶段决策模型。
回溯算法是个 “ 万金油 ” 。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。 尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重 复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要 满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。其中，最优子结构、无后效性跟动态规划中的无异。 “ 贪心选择性 ” 的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

贪心算法存在问题

• 1 不能保证求得的最后解是最佳的；

• 2 不能用来求最大或最小解问题；

• 3 只能求满足某些约束条件的可行解的范围

贪心算法解决钱币找零问题

钱币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？

用贪心算法的思想 ：每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。 在程序中已经事先将Value按照从小到大的顺序排好。

这个代码很简单

private  static  void getNum(int price , int[] values, int[] counts){
        int [] nums = new  int[counts.length];
        for(int j = values.length-1;j>= 0;j--){

            int c= Math.min(price/values[j],counts[j]);

            price = price - c*values[j];

            nums[j] = c;

        }
        for (int i = 0; i < values.length; i++) {
              if (nums[i] != 0) {
                  System.out.println("需要面额为" + values[i] + "的人民币" + nums[i] + "张");
              }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可拆分背包问题

对于0-1背包问题，贪心选择之所以不能得到最优解是因为：它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了
事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。

但是可拆分背包问题就可以使用贪心算法解决，我们只管选择物品装入，装不下则进行拆分

1. 计算每种物品单位重量的价值
2. 将尽可能多的单位重量价值最高的物品装入背包。
3. 若将这种物品全部装入背包后，背包内的物品总重量未超过背包上限，则选择单位重量价值次高的物品并尽可能多地装入背包。
4. 依此策略一直进行下去，直到背包装满为止。

private  static  void  knapsack(float[] goodsWeight, float[] goodValues, int knapsackMaxWeight) {

        float[] goodsX = new float[goodsWeight.length];
        Arrays.sort(goodsWeight);

        int weight = knapsackMaxWeight;
        float allPrice = 0;
        int i = 0;
        for (; i < goodsWeight.length; i++) {
            if (goodsWeight[i] <= weight) {
                goodsX[i] = 1;

                weight -= goodsWeight[i];
                allPrice += goodValues[i];

            } else break;
        }
        //如果可以装入，但是不能整个装入
        if (i < goodsWeight.length) {
            goodsX[i] = weight / goodsWeight[i];  //此时的goodsX[i]接着上面的goodsX[i]
            allPrice = goodsX[i] * goodValues[i];
        }

        for (i = 0; i < goodsWeight.length; i++) {
            if (goodsX[i] < 1) {
                break;
            } else {
                System.out.println("装入的重量为：" + goodsWeight[i] + "\t 价值为：" + goodValues[i]);
            }
        }

        if (goodsX[i] > 0 && goodsX[i] < 1) {  //能装入，但不能整个装入
            System.out.println("装入的重量为：" + goodsX[i] * goodsWeight[i] + "\t 效益为：" + goodValues[i] * goodsX[i] + "是原来的" + goodsX[i]);
        }

        System.out.println("一共装入重量" + knapsackMaxWeight + "\t 总收益为" + allPrice);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

电台覆盖问题

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号

广播台               覆盖地区

K1              "北京", "上海", "天津"

K2              "广州", "北京", "深圳"

K3              "成都", "上海", "杭州"

K4              "上海", "天津"

K5              "杭州", "大连"
1
2
3
4
5
6
7
8
9
10
11

使用贪心算法分析：

1 找到最大覆盖地区，即去除重复的放入coverage集合

2 遍历coverage集合（只要其不为空），求解每个电台覆盖地区与coverage集合的交集，并放入radiosNum map中其中key为电台的编号，value为覆盖地区的数量

3 根据贪心策略从radiosNum 选择最大覆盖地区数量的电台编号放入result集合，并从radiosNum 移除已经选择到的电台和从coverage中删除所有该选择到电台的覆盖地区

4 重复2 - 3 直到coverage集合为空为止

private static  ArrayList<String>  minimumRadioCoverage (HashMap<String, HashSet<String>> radiosMap){

        HashSet<String> coverage = new HashSet<>();

        HashMap<String,Integer>  radiosNum = new HashMap<>();

        radiosMap.forEach((key,value)-> coverage.addAll(value));

        ArrayList<String>  result = new ArrayList<>();

        while (!coverage.isEmpty()){

            radiosMap.forEach((key,value)->{

                value.retainAll(coverage);

                radiosNum.put(key, value.size());//将覆盖的电台及覆盖地区数量放入集合
            });


            //贪心算法的思想，每次选择最大的电台覆盖地区
            Optional<Map.Entry<String, Integer>> maxRadios = radiosNum.entrySet().stream().max(Comparator.comparingInt(Map.Entry::getValue)).stream().findFirst();

            if (maxRadios.isPresent()) {

                String key = maxRadios.get().getKey();
                result.add(key);
                radiosNum.remove(key);
                coverage.removeAll(radiosMap.remove(key));
            }

        }

        return result;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35