数据结构与算法-贪心算法_用贪婪算法实现采花生问题的原理

贪心算法

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

应用场景

• 现有北京，上海，天津，广州，深圳，成都，杭州，大连几个城市需要覆盖广播电台，选取最少的广播电台组使其覆盖上述城市
  选取的组：K1 -> 北京，上海，天津 K2 -> 广州，北京，深圳 K3 -> 成都，上海，杭州 K4 -> 上海，天津 K5- > 杭州，大连

代码实现

public class GreedyAlgorith {

	public static void main(String[] args) {
		
		//创建广播电台，放入到map里
		Map<String, Set<String>> broadcasts = new HashMap<>();
		//将各个电台放入到broadcasts
		Set<String> hashSet1 = new HashSet<>();
		hashSet1.add("北京");
		hashSet1.add("上海");
		hashSet1.add("天津");
		
		Set<String> hashSet2 = new HashSet<>();
		hashSet2.add("广州");
		hashSet2.add("北京");
		hashSet2.add("深圳");
		
		Set<String> hashSet3 = new HashSet<>();
		hashSet3.add("成都");
		hashSet3.add("上海");
		hashSet3.add("杭州");
		
		Set<String> hashSet4 = new HashSet<>();
		hashSet4.add("上海");
		hashSet4.add("天津");
		
		Set<String> hashSet5 = new HashSet<>();
		hashSet5.add("杭州");
		hashSet5.add("大连");
		
		//加入到map
		broadcasts.put("K1", hashSet1);
		broadcasts.put("K2", hashSet2);
		broadcasts.put("K3", hashSet3);
		broadcasts.put("K4", hashSet4);
		broadcasts.put("K5", hashSet5);
		
		//存放所有的地区
		Set<String> allAreas = new HashSet<>();
		allAreas.add("北京");
		allAreas.add("上海");
		allAreas.add("天津");
		allAreas.add("广州");
		allAreas.add("深圳");
		allAreas.add("成都");
		allAreas.add("杭州");
		allAreas.add("大连");
		
		//创建list，存放选择的电台的集合
		List<Object> selects = new ArrayList<>();
		
		//定义临时的集合，存放在遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
		Set<String> tempSet = new HashSet<>();
		
		//定义maxKey，保存在一次遍历过程中，能够覆盖最大地区的电台的Key
		
		
		while(allAreas.size() > 0) {  //如果allAreas不为0，则还没覆盖所有地区
			//如果maxKey不为空，将会加入到selects
			String maxKey = null;
			
			//遍历broadcasts，取出对应的key
			for (String key : broadcasts.keySet()) {
				tempSet.clear();
				Set<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);
				//取出allAreas和areas的交集,交集会赋给tempSet
				tempSet.retainAll(allAreas);
				
				if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
					maxKey = key;
				}
			}
			
			if (maxKey != null) {
				selects.add(maxKey);
				//将maxKey指向的广播电台覆盖的地区从allAreas清除
				allAreas.removeAll(broadcasts.get(maxKey));
				broadcasts.remove(maxKey);
			}
		}
		
		System.out.println(selects.toString());
		
	}

}
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