重新整理数据结构与算法(c#)——算法套路贪心算法[二十八]
2023-09-14 08:59:24 时间
前言
贪心算法,记得学的时候还是大学的时候,再次来总结一下吧。
贪心算法并不是指具体的固定代码,而是指一种思路,加入我们每次都选最好的选择,那么很大可能会得到最好的结果。
题目:
正文
思路,加入把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# WinForm界面美化插件简介
- c# 递归算法
- 算法 – 堆排序(C#)
- c# mysql executenonquery_C#与数据库访问技术之ExecuteNonQuery方法
- 提取HTML代码中文字的C#函数
- asp.net(c#)两种随机数的算法,可用抽考题
- C#数据结构与算法揭秘二
- C#数据结构与算法揭秘二线性结构
- c#通过经纬度查询具体的地址和区域名称
- C#页码导航显示及算法实现代码
- 在C#中对TCP客户端的状态封装详解
- 基于C#委托的深入分析
- 深入C#内存管理以及优化的方法详解
- .netC#实现任意List的笛卡尔乘积算法代码
- C#中实现任意List的全组合算法代码
- c#快速排序算法
- C#的3DES加密解密算法实例代码
- C#正则表达式分解和转换IP地址实例(C#正则表达式大全c#正则表达式语法)
- C#读写注册表的思路及代码
- c#socket网络编程接收发送数据示例代码
- C#获取两个数的最大公约数和最小公倍数示例
- c#获取相同概率随机数的算法代码
- c#生成验证码程序
- C#listview添加combobox到单元格的实现代码
- C#算法之关于大牛生小牛的问题