重新整理数据结构与算法(c#)——算法套路贪心算法[二十八]
2023-09-14 09:01:09 时间
前言
贪心算法,记得学的时候还是大学的时候,再次来总结一下吧。
贪心算法并不是指具体的固定代码,而是指一种思路,加入我们每次都选最好的选择,那么很大可能会得到最好的结果。
题目:
正文
思路,加入把k1到k5轮询一遍,发现k1、k2、k3可以覆盖范围最多,随便取一个,假设取k1。
那么剩下广播地区就余下除了k1的需要覆盖。
那么现在广播k1没了,就剩下k2到k5广播。
继续前面的操作,看下这次谁能覆盖剩下的多,然后就取那一个。
知道所有地区被覆盖为止。
代码实现:
static void Main(string[] args)
{
//初始化电台
Dictionary<string, HashSet<string>> broadcasts = new Dictionary<string, HashSet<string>>();
HashSet<String> k1 = new HashSet<string>();
k1.Add("北京");
k1.Add("上海");
k1.Add("天津");
HashSet<string> k2 = new HashSet<string>();
k2.Add("广州");
k2.Add("北京");
k2.Add("深圳");
HashSet<string> k3 = new HashSet<string>();
k3.Add("成都");
k3.Add("上海");
k3.Add("杭州");
HashSet<string> k4 = new HashSet<string>();
k4.Add("上海");
k4.Add("天津");
HashSet<string> k5 = new HashSet<string>();
k5.Add("杭州");
k5.Add("大连");
broadcasts.Add("k1",k1);
broadcasts.Add("k2", k2);
broadcasts.Add("k3", k3);
broadcasts.Add("k4", k4);
broadcasts.Add("k5", k5);
//初始化要覆盖的地区
HashSet<String> allAreas = new HashSet<String>();
allAreas.Add("北京");
allAreas.Add("上海");
allAreas.Add("天津");
allAreas.Add("广州");
allAreas.Add("深圳");
allAreas.Add("成都");
allAreas.Add("杭州");
allAreas.Add("大连");
//创建ArrayList, 存放选择的电台集合
List<String> selects = new List<String>();
HashSet<String> tempSet = new HashSet<String>();
string maxKey = string.Empty;
while (allAreas.Count != 0)
{
maxKey = string.Empty;
int maxNum = 0;
foreach (String key in broadcasts.Keys)
{
tempSet.Clear();
tempSet.UnionWith(allAreas);
tempSet.IntersectWith(broadcasts[key]);
if (tempSet.Count>0&&(maxKey==string.Empty||tempSet.Count> maxNum))
{
maxKey = key;
maxNum = tempSet.Count;
}
}
//选好后移除
if (maxKey != string.Empty)
{
selects.Add(maxKey);
allAreas.ExceptWith(broadcasts[maxKey]);
}
}
foreach (var data in selects)
{
Console.WriteLine(data);
}
Console.Read();
}
结果:
贪心算法不一定是最优解,但是这种解法比较快,不然要把所有的情况考虑进去。
相关文章
- C#最短路径算法demo
- c#数组赋初值_C#数组初始化
- c# mysql executenonquery_C#与数据库访问技术之ExecuteNonQuery方法
- C#-FileSystemWatcher文件和文件夹监控
- c# 多线程并发-金三银四面试:C#.NET面试题高级篇2-多线程
- 【地铁上的Redis与C#】数据类型(十三)--综合案例
- 【Unity3D】Unity 脚本 ① ( 创建 C# 脚本 | Visual Studio 2019 中打开 C# 脚本 | 编译 C# 脚本 | 挂载 C# 脚本到游戏物体 | 运行脚本 )
- C#/.NET值类型
- 常用正则常用的C#正则表达式
- C#数据结构与算法揭秘三链表
- C#数据结构与算法揭秘四双向链表
- C#中城市线路图的纯算法以及附带求极权值
- 解析C#中用Process类杀死进程,执行命令的深入分析
- 解析C#彩色图像灰度化算法的实现代码详解
- 探讨c#中的unchecked是什么意思,起什么作用?
- 分享C#操作内存读写方法的主要实现代码
- 在C#中创建和读取XML文件的实现方法
- c#冒泡排序算法(BubbleSort)附实例代码
- C#泛型的简单理解(安全、集合、方法、约束、继承)分享
- 操作xml,将xml数据显示到treeview的C#代码
- C#判断数据类型的简单示例代码
- c#使用ManagedWifi查看当前Wifi信号并选择wifi的示例
- C#排序算法的比较分析
- C#算法设计之关于1000瓶水的问题
- C#实现排列组合算法完整实例
- C#中的匿名方法实例解析
- C#键盘输入回车键实现点击按钮效果的方法