算法---貪心算法

在我們日常生活當中,很多地方都用到了貪心算法的思想,只是我們並未發覺,現在就來說說什麼是貪心算法吧。

什麼是貪心算法?

貪心算法又被稱之為“貪婪算法”。它是指在對問題進行求解時,在每一步的選擇中找到最優解,也稱之為局部最優解。貪心算法並不考慮整體情況。所以貪心算法所得到的結果最終可能並不是最優的結果。

下面來做一個案例,來體會貪心算法。集合覆蓋問題

算法---貪心算法

貪心法解決集合覆蓋問題

問題描述:假設存在下面要付費的廣播電臺,以及廣播信號可以覆蓋的區域。如何選擇最少的廣播電臺,讓所有的地區都可以收到信號

算法---貪心算法

思路:

  1. 遍歷所有的廣播電臺,找到一個包含了未覆蓋區域最多的電臺,maxValue
  2. 將這個電臺添加到集合中。在allArea中去掉此電臺覆蓋的區域
  3. 重複步驟
<code>package com.algorithm.greedy;

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



//使用貪心算法解決集合覆蓋的問題
public class greedyAlgorithm {
	
	//用來存儲每個廣播電臺分別都對應那些城市
	static HashMap> broadcast=new HashMap<>();
	
	//存放電臺覆蓋的區域
	static HashSet allAreas=new HashSet();
	
	
	public static void main(String[] args) {
		init();
		countArea();
		select();
		
	}
	
	//初始化,將電臺信息加入到braoadcast中
	public static void init() {
		HashSet set1=new HashSet<>();
		set1.add("北京");
		set1.add("上海");
		set1.add("天津");
		
		HashSet set2=new HashSet<>();
		set2.add("廣州");
		set2.add("北京");
		set2.add("深圳");
		
		HashSet set3=new HashSet<>();
		set3.add("成都");
		set3.add("上海");
		set3.add("杭州");
		
		HashSet set4=new HashSet<>();
		set4.add("上海");
		set4.add("天津");
		
		HashSet set5=new HashSet<>();
		set5.add("杭州");
		set5.add("大連");
		
		broadcast.put("K1", set1);
		broadcast.put("K2", set2);
		broadcast.put("K3", set3);
		broadcast.put("K4", set4);
		broadcast.put("K5", set5);
		
	}
	
	//將電臺覆蓋的區域加入到allArea中
	public static void countArea() {
		for(String key : broadcast.keySet()) {
			for(String area: broadcast.get(key)) {
				allAreas.add(area);
			}
		}
	}
	
	//選擇電臺
	public static void select() {
		//用來存放選擇了哪些電臺
		ArrayList selects=new ArrayList<>();
		
		HashSet temp=new HashSet();
		
		String maxKey=null; //找到當前情況下最優的的那個電臺
		
		//當還有地區沒有被覆蓋掉時
		while(allAreas.size()!=0) {
			
			maxKey=null;
			for(String key: broadcast.keySet()) {
				//將temp置空
				temp.clear();
				temp.addAll(broadcast.get(key));
				//求交集後賦值給temp
				temp.retainAll(allAreas);
				if(temp.size()>0&&(maxKey==null||temp.size()>broadcast.get(maxKey).size())) {
					maxKey=key;
				}
			}
			if(maxKey!=null) {
				selects.add(maxKey);
				allAreas.removeAll(broadcast.get(maxKey));
			}
		}
		
		System.out.println("得到的選擇結果"+selects);
		
	}

}/<code>


算法---貪心算法

以上就是貪心算法的講解。在之後,我會發布一些相關的使用貪心算法求解的算法題。歡迎大家評論討論。


分享到:


相關文章: