Java 数据结构与算法系列精讲之贪心算法

Java 数据结构与算法系列精讲之贪心算法

概述

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

贪心算法

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

贪心算法的优缺点:

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

电台覆盖问题

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

广播台覆盖地区K1北京, 上海, 天津K2北京, 广州, 深圳K3上海, 杭州, 成都K4上海, 天津K5杭州, 大连

贪心算法的核心思想:

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

代码实现

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashMap;

import java.util.HashSet;

public class 贪心算法 {

// 集合, 存放广播台

static HashMap> broadcasts = new HashMap<>();

// 集合, 存放地区

static HashSet areas = new HashSet();

// 贪心算法

public static ArrayList Greedy() {

// 创建数组存放结果

ArrayList 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 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 K1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));

HashSet K2 = new HashSet<>(Arrays.asList("北京", "广州", "深圳"));

HashSet K3 = new HashSet<>(Arrays.asList("上海", "杭州", "成都"));

HashSet K4 = new HashSet<>(Arrays.asList("上海", "天津"));

HashSet K5 = new HashSethttp://<>(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 result = Greedy();

System.out.println(result);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。