问题描述

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号。

思路分析

目前并没有算法可以快速计算得到准确的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:

1. 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台（此电台可能包含一些已覆盖的地区，但没有关系）
2. 将这个电台加入到一个集合中（比如ArrayList)，想办法把该电台覆盖的地区在下次比较时去掉）
3. 重复第1步直到覆盖了全部的地区

   举例分析

   先把上面的所有城市统计出来，有如下这些城市，可以装在一个集合里面，下文就叫AllCity

   北京，上海，天津，广州，深圳，成都，杭州，大连

现在遍历全部广播电台，找到未覆盖城市最多的电台，比如现在还未覆盖的城市有上面的8个，K1覆盖地区 北京，上海，天津，都还在AllCity里面，所以K1未覆盖城市数量为3，所以各个电台未覆盖地区的数量如下

• K1：3
• K2：3
• K3：3
• K4：2
• K5：2

根据贪心算法，每次找到最优的解，肯定想要一次性多覆盖点城市啊K1，K2，K3都是3个城市，就选K1，然后把K1装到被选择电台的集合（KList）里面。
然后在AllCity里面去掉K1的个城市，现在AllCity还剩下这5个城市

广州，深圳，成都，杭州，大连

再次统计出电台最多覆盖AllCity的情况

• K1：0
• K2：2
• K3：2
• K4：0
• K5：2

这次选K2，跟上面的操作一样，K2放入KList，在AllCity里面去掉K2的城市：

成都，杭州，大连

再次统计

• K1：0
• K2：0
• K3：2
• K4：0
• K5：2

……就这样统计，直到AllCity全部都没了，KList里面就是优解（不一定是最优）

代码

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            //创建广播电台
            Dictionary<string, List<string>> broadcasts = new Dictionary<string, List<string>>();
            //将各个电台放入到broadcasts
            List<string> K1Citys = new List<string>();
            K1Citys.Add("北京");
            K1Citys.Add("上海");
            K1Citys.Add("天津");
            List<string> K2Citys = new List<string>();
            K2Citys.Add("广州");
            K2Citys.Add("北京");
            K2Citys.Add("深圳");
            List<string> K3Citys = new List<string>();
            K3Citys.Add("成都");
            K3Citys.Add("上海");
            K3Citys.Add("杭州");
            List<string> K4Citys = new List<string>();
            K4Citys.Add("上海");
            K4Citys.Add("天津");
            List<string> K5Citys = new List<string>();
            K5Citys.Add("杭州");
            K5Citys.Add("大连");
            broadcasts.Add("K1", K1Citys);
            broadcasts.Add("K2", K2Citys);
            broadcasts.Add("K3", K3Citys);
            broadcasts.Add("K4", K4Citys);
            broadcasts.Add("K5", K5Citys);
            //存放所有的地区
            List<string> AllCity = new List<string>();
            AllCity.Add("北京");
            AllCity.Add("上海");
            AllCity.Add("天津");
            AllCity.Add("广州");
            AllCity.Add("深圳");
            AllCity.Add("成都");
            AllCity.Add("杭州");
            AllCity.Add("大连");
            //创建一个存放选择的电台集合
            List<string> KList = new List<string>();
            //定义一个临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖地区的交集
            List<string> temp = new List<string>();
            //定义一个maxKey，保存在遍历过程中能够覆盖最大未覆盖的地区对应的电台的key
            //如果maxKey不为null,则会加入到KList
            string maxKey = null;
            int maxCount = 0;
            while (AllCity.Count != 0)//如果AllCity不为0的话，则表示还没有覆盖到所有的地区
            {
                //每一次循环要把maxKey清空
                maxKey = null;
                foreach(var key in broadcasts.Keys)
                {
                    temp.Clear();
                    //当前这个key能覆盖到的地区
                    List<string> city = broadcasts[key];
                    temp.AddRange(city);
                    //保留在所有城市中未覆盖的地区，求出广播台的地区和全部城市的交集
                    foreach (var c in city)
                        if (!AllCity.Contains(c))
                            temp.Remove(c);
                    //如果广播台在所有城市中未覆盖的区域，不是0，且第一次执行或者现在这个广播台比上次最大的广播台的次数还多，就从新定义广播台
                    //这次体现了贪心
                    if (temp.Count > 0 && (maxKey == null || temp.Count > maxCount))
                    {
                        maxKey = key;
                        maxCount = temp.Count;//保存上一次的最大的数量
                    } 
                }
                if (maxKey != null)
                {
                    KList.Add(maxKey);
                    foreach (var a in broadcasts[maxKey])
                        if (AllCity.Contains(a))
                            AllCity.Remove(a);
                }
            }
            Console.WriteLine("结果");
            foreach(var a in KList)
            {
                Console.Write(a+"  ");
            }
        }
    }
}