集合覆盖问题算法程序问题。我画框的地方是怎么算出来的?求过程。

内容提示:集合覆盖问题算法程序覆盖问题的模型与算法

文档格式:PDF| 浏览次数:37| 上传日期: 12:42:52| 文档星级:?????

全文阅读已结束如果下载本文需要使用

该用户还上传叻这些文档

在《算法图解》里面有一个蛮有意思的小案例背景是一个广播节目,要让全美的50个周的听众都能够听到但是每个电台可能覆盖多个州,每在一个电台播出就需要一笔費用所以就是从成本的角度来看,怎么尽可能在所有的州都播出这是一个典型的集合覆盖问题算法程序覆盖的问题,而且在我们的生活中算是比较典型

比如我们先缩小范围,指定5个州那么50个州也是同样的算法。

有的同学可能对这些州没概念这个简称就跟京代表北京,鲁代表山东甘代表甘肃一样,细细一看都是西部的一些州。

如何使用贪心算法呢就是选择覆盖尽可能多的州的电台,然后逐步縮小范围那么覆盖面广的州所对应的电台就优先被选中,依次类推

程序的实现是指定了一个集合覆盖问题算法程序states_need,里面包含所有的州每个电台对应的州是通过初始化的数组元素来实现的,按照一二三四五的顺序来命名当然实际上这种元素的排列set不是按照数组名的順序,在这个场景里是kfive,ktwo,kthree,kone,kfour

然后逐步缩小范围来收敛里面比较特别的一点就是集合覆盖问题算法程序的运算,使用了 & ,得到的是交集如果是並集是 |,差集是 -

我要回帖

更多关于 集合覆盖问题贪心算法 的文章

 

随机推荐