概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

贪心算法

贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果.

贪心算法的优缺点:

• 优点: 贪心算法的代码十分简单
• 缺点: 很难确定一个问题是否可以用贪心算法解决

电台覆盖问题

假设存在以下的广播台, 以及广播台可以覆盖的地区:

贪心算法的核心思想:

• 把所有需要覆盖的地区取集合
• 从电台中取覆盖集合中地区最多的一个
• 集合中去除已覆盖地区, 继续匹配

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class 贪心算法 {

    // 集合, 存放广播台
    static HashMap<String, HashSet<String>> broadcasts = new HashMap<>();

    // 集合, 存放地区
    static HashSet<String> areas = new HashSet<String>();

    // 贪心算法
    public static ArrayList<String> Greedy() {

        // 创建数组存放结果
        ArrayList<String> selects = new ArrayList<>();

        // 循环直至地区都覆盖
        while (areas.size() != 0) {

            // 存放交集最大的广播台
            String maxKey = null;

            // 存放交集最大的值
            int maxKeySize = 0;

            // 遍历每个剩余电台
            for (String key : broadcasts.keySet()) {

                // 取出交集个数
                int currSize = getRetainSize(key);

                // 替换当前最大
                if (currSize > 0 && currSize > maxKeySize) {
                    maxKey = key;
                    maxKeySize = currSize;
                }
            }


            // 添加广播台到结果
            selects.add(maxKey);

            // 移除广播台
            areas.removeAll(broadcasts.get(maxKey));
        }

        return selects;
    }

    // 剩余数量
    public static int getRetainSize(String key) {

        // 如果为空返回0
        if (key == null) return 0;

        // 存放key对应的地区集合
        HashSet<String> tempSet = new HashSet<>();

        // 取key对应的地区
        tempSet.addAll(broadcasts.get(key));

        // 取交集
        tempSet.retainAll(areas);

        return tempSet.size();
    }

    public static void main(String[] args) {

//        | K1 | 北京, 上海, 天津 |
//        | K2 | 北京, 广州, 深圳 |
//        | K3 | 上海, 杭州, 成都 |
//        | K4 | 上海, 天津 |
//        | K5 | 杭州, 大连 |


        // 创建广播台
        HashSet<String> K1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));
        HashSet<String> K2 = new HashSet<>(Arrays.asList("北京", "广州", "深圳"));
        HashSet<String> K3 = new HashSet<>(Arrays.asList("上海", "杭州", "成都"));
        HashSet<String> K4 = new HashSet<>(Arrays.asList("上海", "天津"));
        HashSet<String> K5 = new HashSet<>(Arrays.asList("杭州", "大连"));

        // 加入map
        broadcasts.put("K1", K1);
        broadcasts.put("K2", K2);
        broadcasts.put("K3", K3);
        broadcasts.put("K4", K4);
        broadcasts.put("K5", K5);

        areas.addAll(K1);
        areas.addAll(K2);
        areas.addAll(K3);
        areas.addAll(K4);
        areas.addAll(K5);

        // 调试输出
        System.out.println(broadcasts);
        System.out.println(areas);

        ArrayList<String> result = Greedy();
        System.out.println(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
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
 

文章来源: iamarookie.blog.csdn.net，作者：我是小白呀，版权归原作者所有，如需转载，请联系作者。

原文链接：iamarookie.blog.csdn.net/article/details/122120409