Shulou(Shulou.com)06/01 Report--

Most people do not understand the knowledge points of this "Java greedy algorithm instance Analysis" article, so the editor summarizes the following contents, detailed contents, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "Java greedy algorithm instance Analysis" article.

Greedy algorithm

Greedy algorithm (Greedy Algorithm) refers to the best or best choice in the current state in every step of the selection, hoping to lead to the best or best result. The results obtained by greedy algorithm locking are not necessarily optimal, but they are relatively nearly optimal.

Advantages and disadvantages of greedy algorithms:

Advantages: the code of greedy algorithm is very simple.

Disadvantages: it is difficult to determine whether a problem can be solved by greedy algorithm

Radio coverage problem

Suppose the following radio stations exist, and the areas that can be covered by the radio stations:

Radio stations cover K1 Beijing, Shanghai, Tianjin K2 Beijing, Guangzhou, Shenzhen K3 Shanghai, Hangzhou, Chengdu K4 Shanghai, Tianjin K5 Hangzhou, Dalian

The core idea of greedy algorithm:

Collect all the areas that need to be covered

Get the largest number of areas in the coverage set from the radio station

Remove the covered areas from the collection and continue to match

The code implements the import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.HashSet;public class greedy algorithm {/ / collection, which stores the broadcast station static HashMap broadcasts = new HashMap (); / / collection, and the storage area static HashSet areas = new HashSet () / / greedy algorithm public static ArrayList Greedy () {/ / create an array to store the result ArrayList selects = new ArrayList (); / / loop until the region covers while (areas.size ()! = 0) {/ / stores the broadcaster String maxKey = null with the largest intersection / / store the maximum intersection value int maxKeySize = 0; / / traverse each remaining radio for (String key: broadcasts.keySet ()) {/ / take out the number of intersections int currSize = getRetainSize (key) / / replace the current maximum if (currSize > 0 & & currSize > maxKeySize) {maxKey = key; maxKeySize = currSize;}} / / add the broadcast station to the result selects.add (maxKey) / / remove the radio station areas.removeAll (broadcasts.get (maxKey));} return selects;} / / remaining quantity public static int getRetainSize (String key) {/ / return 0 if (key = = null) return 0 if empty; / / store the region set HashSet tempSet = new HashSet () corresponding to key / / take the region corresponding to key tempSet.addAll (broadcasts.get (key)); / / take intersection tempSet.retainAll (areas); return tempSet.size () } public static void main (String [] args) {/ / | K1 | Beijing, Shanghai, Tianjin | / / | K2 | Beijing, Guangzhou, Shenzhen | / / | K3 | Shanghai, Hangzhou, Chengdu | / / | K4 | Shanghai, Tianjin | / | K5 | Hangzhou Dalian | / / create a radio station HashSet K1 = new HashSet (Arrays.asList ("Beijing", "Shanghai", "Tianjin") HashSet K2 = new HashSet (Arrays.asList ("Beijing", "Guangzhou", "Shenzhen"); HashSet K3 = new HashSet (Arrays.asList ("Shanghai", "Hangzhou", "Chengdu")); HashSet K4 = new HashSet (Arrays.asList ("Shanghai", "Tianjin"); HashSet K5 = new HashSet ("Hangzhou", "Dalian")) / add 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); / / debug output System.out.println (broadcasts); System.out.println (areas); ArrayList result = Greedy (); System.out.println (result) }} the above is about the content of this article on "instance Analysis of Java greedy algorithm". I believe we all have some understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about the relevant knowledge, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.