闭区间线段覆盖问题贪心算法

‘壹’ 线段覆盖问题 算法及程序

我的算法:
我采用贪心的算法,
按照左端点排序,
建立一个以线段右端点为关键字的大根堆.
依次尝试插入线段,
对于当前的一个线段,
如果能够覆盖,显然我们选择覆盖,
而如果不能覆盖,
我们进行一下讨论.
首先我们需要知道
(1)
如果线段发生相交,
那么只可能是两条线段相交:
理由:
对于前面的所有线段,贪心法保证,也显然,已经满足两两不相交了,
那么如果当前的线段,和另外两条线段相交,
则必然将一条线段包含,
而我们按照线段左端点排序,
按次序尝试覆盖,
因此这种情况是不存在的.
那么我们假设当前的线段是
[L0,
R0]
发生相交的线段是
[L1,
R1]
即有
L0
>=
L1
R0
<=
R1
这两条线段是不能共存的.
显然,我们要从中留下一个而舍去一个,
舍去哪个呢?
就应该选择右端点小的那个!
为什么?
因为右端点越靠左,对后面的线段的覆盖产生的影响(就是发生覆盖的机会)就越小!
很直观的,
我们可以知道这种贪心法的正确性.
问题就解决了
时间复杂度
O(N
log
N)
我写的代码:
#include
#include
#include
#include
using
namespace
std;
const
int
maxn
=
10010;
struct
event
{
int
l,
r;
}e[maxn];
struct
__Comp
{
inline
int
operator()
(const
event
&a,
const
event
&b)
const
{
return
a.r
<
b.r;
}
};
priority_queue
,
__Comp>
hp;
int
n,
l,
r;
inline
int
comp(const
event
&a,
const
event
&b)
{return
a.l
<
b.l;}
int
main()
{
scanf("%d",
&n);
for
(int
i=0;i
?r};
}sort(e,
e+n,
comp);
for
(int
i=0;i
=
hp.top().r)
hp.push(e[i]);
else
if
(hp.top().r
>
e[i].r)
{
hp.pop();
hp.push(e[i]);
}
}
printf("%d\n",
hp.size());
scanf("%*s");
}

‘贰’ 近似算法的集合覆盖问题的近似算法

问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。
集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X= 。对于F中的一个子集CF，若C中的X的子集覆盖了X，即X= ，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得
|C*|=min{|C||CF且C覆盖X}
集合覆盖问题举例：用12个黑点表示集合X。F={S1,S2,S3,S4,S5,S6,}，如图所示。容易看出，对于这个例子，最小集合覆盖为：C={S3,S4,S5,}。
集合覆盖问题近似算法——贪心算法
Set greedySetCover (X,F)
{
U=X；
C=；
while (U !=) {
选择F中使|S∩U|最大的子集S；
U=U-S；
C=C∪{S}；
}
return C；
}
算法的循环体最多执行min{|X|，|F|}次。而循环体内的计算显然可在O(|X||F|)时间内完成。因此，算法的计算时间为O(|X||F|min{|X|，|F|})。由此即知，该算法是一个多项式时间算法。

‘叁’ 关于线段覆盖的问题

如果一个点在一条线段上（包括这个点是线段端点的情况），我们说“这条线段覆盖了这个点”。

‘肆’ 闭区间覆盖问题的贪心选择性如何证明

不会呀！你问问老师吧！~~~

‘伍’ 怎样用闭区间套定理证明有限覆盖定理

所谓有限覆盖定理，是指：对于有界闭区间[a，b]的一个（无限）开覆盖H中，总能选出有限个开区间来覆盖[a，b]。
这一问题可用区间套定理来证明。（区间套定理：若[an,bn]是一个区间套，则在实数系中存在唯一一点C，使对任何n都有c属于[an,bn].{an}单调递增，{bn}单调递减，都以c为极限。）

证明：用反证法 假定不能用H中有限个开区间来覆盖[a,b].
将[a,b]等分为两个子区间，则其中至少有一个子区间不能用H中有限个开区间来覆盖。记这个子区间为[a1,b1],则[a1,b1]包含于[a,b],且b1-a1=(b-a)/2.
再将[a1,b1]等分为两个子区间，同样，其中至少有一个不能用H中有限个开区间覆盖。记这个子区间为[a2,b2],则[a2,b2]包含于[a1,b1],且b2-a2=(b-a)/2^2.
重复以上步骤并不断进行下去，则可得到区间列{[an,bn]},它满足区间套条件，且其中每一个闭区间都不能用H中有限个开区间来覆盖。
但，由区间套定理，存在唯一点c属于所有区间[an,bn].由于H是[a,b]的开覆盖，一定存在H中的一个开区间(a0,b0),使c属于(a0,b0).即a0<c<b0.而{an}，{bn}都以c为极限，即知，存在N，当n>N时,a0<an<=c<=bn<b0.这表明，只用开区间(a0,b0)就覆盖了区间[an,bn].
这与挑选[an,bn]时假设“[an,bn]不能用H中有限个开区间覆盖”矛盾。从而证得，必存在H中有有限个开区间能覆盖[a,b].

‘陆’ 贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。

3.2.2.1 贪心算法1

第一步:设置一个记录三角剖分中边的数组T。

第二步:计算点集S中所有点对之间的距离d(p_i，p_j)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d₁，d₂，…，d_n(n-1)/2，相应的线段记为e₁，e₂，…，e_n(n-1)/2，将这些线段存储在数组E中。

第三步:从线段集E中取出长度最短的边e₁存到T中作为三角剖分的第一条边，此时k=1。

第四步:依次从E中取出长度最短的边e_k，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除e_k。这一步运行到S中没有边为止，即至k=n(n-1)/2。

第五步:输出T。

该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n²lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n³)。

3.2.2.2 贪心算法2

第一步:求点集的凸壳，设凸壳顶点为p₁，p₂，…，p_m，凸壳的边为e₁，e₂，…，e_m。并将凸壳顶点按顺序连接成边的e_i加入T(三角剖分的边集合)，并且e_i的权值被赋为1。凸壳内点的集合为S₁={p_m+1，p_m+2，…，p_n}。

第二步:从内部点S₁中任取一点p_i，求与p_i距离最近的点p_j，将线段 存入T。

第三步:求与p_j距离最近的点(除点p_i外)，设为p_k，并将线段 加入T，并将这些边的权值设为1，而w_ij、w_jk和w_ki的值加1，即为2。边的权值为2则表示该边为两个三角形共有。

第五步:对权值为1的边(除e₁，e₂，…，e_m外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1。

第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e₁，e₂，…，e_m外)。

贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求p_k要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)

‘柒’ 贪心算法及其应用

求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。

比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装100KG重量的袋子，怎么装才能使得袋子中的豆子价值最大？

我们首先看看这个问题是否符合贪心算法的使用场景？限制值是袋子100KG，期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法，每一个步骤都寻找当下的最优解，怎么做呢？

把仓库里面的每种豆子价值除以重量，得出每种豆子的单价，那么当下的最优解，肯定是尽可能最多地装单价最贵的，也就是先把20KG的黄豆都装上，然后再把30KG的绿豆都装上，再装50KG的红豆，那么此时正好装满袋子，总价值将是270元，这就是通过贪心算法求解的答案。

贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证，我们不用那样，只要心里举几个例子，验证下是否比它更好即可，如果举不出例子，那么就可以认为这就是最优解了。

虽然贪心算法虽然在大部分实践场景中都能得到最优解，但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径，那么答案肯定就是S->A->E->T，总代价为1+4+4=9；

然而，实际上的最短路径是S->B->D->T，总代价为6。

所以，不能所有这类问题都迷信贪心算法的求解，但其作为一种算法指导思想，还是很值得学习的。

除了以上袋子装豆子的问题之外，还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题，即找到问题的限制值和期望值。

我们有m个糖果要分给n个孩子，n大于m，注定有的孩子不能分到糖果。其中，每个糖果的大小都不同，分别为S1,S2,S3...,Sm，每个孩子对糖果的需求也是不同的，为N1,N2,N3...,Nn，那么我们如何分糖果，才能尽可能满足最多数量孩子的需求？

这个问题中，限制值是糖果的数量m，期望值满足最多的孩子需求。对于每个孩子，能用小的糖果满足其需求，就不要用大的，避免浪费。所以我们可以给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。

我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张，现在要购买一个价值K元的东西，请问怎么才能适用最少的纸币？

这个问题应该不难，限制值是各个纸币的张数，期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱，当再加一张100元就超过K时，就更换小面额的，直至正好为K元。

对于n个区间[L1,R1],[L2,R2]...[Ln,Rn]，我们怎么从中选出尽可能多的区间，使它们不相交？

我们需要把这个问题转换为符合贪心算法特点的问题，假设这么多区间的最左端点是Lmin，最右端点是Rmax，那么问题就是在[Lmin,Rmax]中，选择尽可能多的区间往里面塞，并且保证它们不相交。这里，限制值就是区间[Lmin,Rmax]，期望值就是尽可能多的区间。

我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。

贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。

‘捌’ 求一个算法(贪心算法)

首先,无所谓哪里密集哪里不密集的说法,这是人为的区分,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了.
既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走，思想如下:
判断当前格子右、下两个相邻的格子是否有金块，情形如下：
1）如果一个有一个没有，则往有金块的格子走
2）如果都没有或都有，则需要判断往哪个方向走能更快的拾到下一个金块，方法如下：
让机器人假设地各往两个方向走一步，然后对当前格子作判断情形如下：
A)一个格子继续走能拾到金块，另一个不能，则上一步往该格子走
B)如果仍旧都有或都没有，重复2）直到找到符合A）的情形。

假设棋盘是N*N个格子，则贪心算法最坏的情形是要遍历整个棋盘，比如只有第一个格子有金块时，就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4*N个格子。
时间复杂度上来算的话，应该是O（nLogn）

‘玖’ 求贪心算法题（Pascal）

《编程之美》里面有一道买书问题的贪心算法。
题目是这样的：
在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。上柜的《哈利波特》平装本系列中，一共有五卷。假设每一卷单独销售均需8欧元 。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中，根据购买的卷数及本数，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望计算出的总额尽可能的低。
要求根据以上需求，设计出算法，能够计算出读者所购买一批书的最低价格。

‘拾’ 对于二分图覆盖问题设计一种贪婪启发算法，贪婪准则是：如果B中某一个顶点被A中一个顶点覆盖，选择A中这个

西南的吧，呵呵，这个用的是匈牙利算法，参照．
bool g[][];
int xM[], yM[];
bool chk[];

bool find(int u)
{
int v;
for(v=1; v<=M; v++)
if(g[u][v] && !chk[v])
{
chk[v] = true;
if(yM[v] == -1 || find(yM[v]))
{
yM[v] = u;
xM[u] = v;
return true;
}
}
return false;
}
int MaxMatch()
{
int u, ret = 0;
memset(xM, -1, sizeof(xM));
memset(yM, -1, sizeof(yM));
for(u= 1;u<=N; u++) {
if(xM[u] == -1)
{
memset(chk, false, sizeof(chk));
if(find(u)) ret++;
}
}
return ret;
}