## 贪心算法         

引入

FatMouse's Trade

老鼠准备了5公斤的猫粮

3个房间

7公斤的豆子，2公斤的猫粮

5公斤的豆子，2公斤的 猫粮

4公斤的豆子，3公斤的猫粮

按比例，在第2个房间，如果给我1公斤猫粮给你2.5公斤的豆子

什么叫计算思维

根据性价比排序，从高到低，分别去做交易

在对问题求解时，总是作出当前看来最好的选择。

所作出的仅仅是局部最优解（是否为全局最优需要证明。）

### 基本思想

和动态规划：相似点：能求解的问题都具有最优子结构性质。

不同点：求最优解的选择策略不一样。

重叠子问题：

子问题空间足够小，这样才能够产生足够的相同子问题。

不同子问题总数是输入规模的多项式函数。如果递归过程能够反复求解

### 贪心算法基本特点

求解最优化问题时对于动态规划求解可以用更简单的方法

贪心算法每一步都做出当时看起来最优的选择，即局部最优解；通过局部最优解导出全局最优解

从一个初始解除法，每一阶段都根据贪心策略来做出当前最优的决策，逐步逼近给定的目标，尽可能地求得更好地解。

当到达算法中的某一步不能再继续前进时，算法终止

### 求解步骤

1. 最优化问题为你做出选择后只有一个子问题需要求解。
2. 证明每次做出贪心选择后，原问题总是有最优解，所以贪心选择总是安全的。
3. 证明做出贪心选择后的子问题和贪心选择一起构成原问题的最优解，即原问题具有最优子结构。

能够用贪心算法求解的问题具有贪心选择性质和最优子结构。

定义：

1、从初始空解出发{}，采用逐步构造最优解的方法向目标前进，每一步决策产生n元组解$(x0,x1,….,x_{n-1})$的一个分量

2、每一步的选择准则被称为最优量度标准（贪心准则）（局部最优策略），在选择解分量的过程中，添加新的解分量Xk后，形成的不分解$(x0,x1,…,xk)$不违反可行解的约束条件

3、每一次贪心选择都将所求问题简化为规模更小的子问题，将所有部分解综合起来，期望通过每次所做的局部最优选择产生一个全局最优解。 

 

 ![image-20260301170527317](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301170527317.png)

分解：将原问题分解成若干个相互独立的阶段

解决：对于每个阶段依据贪心策略进行

特点：每个阶段面临选择时，贪心算法都做出当前来讲是最有利的

选择算法简单，选择一旦做出不可更改，即不允许回溯

根据贪心策略来逐步构造问题的解

贪心算法效率高，但不稳定。（无法求得最优解）

求解的问题应该具有的性质

**贪心选择性质(Greedy-choice property)**

可以通过作出局部最优（贪心）选择来构造全局最优解。

多个局部结构可以得到整体最优

当前看来是最好的选择，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。

贪心算法和动态规划的对比：

- 动态规划的选择依赖于子问题的解，所以一般采用自底向上的方法求解问题。
- 贪心算法不依赖于子问题的解，所以一般采用自顶向下的方法求解问题。

因此需要证明设计的确实是整体最优解，使用贪心算法前，我们必须证明每个步骤做出贪心选择能生成全局最优解。

如果我们进行贪心选择时不得不考虑众多选择，我们必须提高进行贪心选择的效率。通过对输入数据进行**预处理(preprocess)**或者选择合适的数据结构（通常是优先队列），我们可以快速做出贪心选择，从而得到高效的算法。

**最优子结构(optimal substructure)**：如果一个问题的最优解包含其子问题的最优解，那么称该问题具有最优子结构。

贪心算法通常采用一个非常直接的方法运用最优子结构，假定通过对原问题的贪心选择就可以得到子问题，我们只需要证明做出贪心选择后的子问题和贪心选择一起构成原问题的最优解。该方法隐式地运用了归纳法，证明了每一步贪心选择都能构成原问题的最优解。

原问题的最优解一定包含其子问题的最优解

采用反证法

### 一般过程



```
SolutionType Greedy(SType a[],int n)
//假设解向量(xe,x1,..,xn.1)类型为SolutionType，其分量为SType类型
( SolutionType x={};//初始时，解向量不包含任何分量
for (int i=0;i<n;i++){//执行n步操作
SType xi=select(a);//从输入a中选择一个当前最好的分量
if (Feasiable(xi))//判断xi是否包含在当前解
solution=Union(x,xi);//将xi分量合并形成x
}
return x;//返回生成的最优解
}
```

### 典型问题

#### 活动选择问题

假设有一个需要使用某一资源的n个活动所组成的集合S，S={1，...，n}。

该资源任何时刻只能被一个活动所占用，活动i有一个开始时间bi,和结束时间ei，(bi<ei,[bi,ei))，其执行时间为ei-bi，假设最早活执行时间为0。

一旦某个活动开始执行，中间不能被打断，直到其执行完毕。若活动i和活动j有bi≥ej,或bj≥ei，则称这两个活动兼容。

设计求一种最优活动安排方案，使得所有安排的活动个数最多. 

 问题求解:假设活动时间的参考原点为0。一个活动i(1≤i≤n)用一个区间[bi,ei)表示，当活动按结束时间(右端点)递增排序后，两个活动[bi,ei)[bj，ej)兼容(满足bi≥ej,或bj≥ei)实际就是指它们不相交。

用数组A存放所有的活动，A[i].b(1≤i≤n)，存放活动起始时间，A[i].放存活动结束时间。

采用贪心策略:每一步总是选择这样一个活动来占用资源，它能够使得余下的朱调度的时间最大化，使得兼容的活动尽可能多。

为此先按活动结束时间递增排序，在从头开始选择兼容活动，得到最大兼容活动子集。由于按结束时间递增排序，每次总是选择具有最早完成的兼容活动加入集合，所以选择的兼容活动为未安排的活动留下尽可能多的时间，使得剩余的可安排时间段极大化，以便安排尽可能多的活动。

```
//问题表示
struct Action//活动的类型声明
{int b;//活动起始时间

int e;//活动结束时间


bool operator <(const Action &c )const //重载<关系函数
{return e<=s.e;}//用于按活动结束时间递增排序
};
int n=11;
Action A[]={(0),(1,4},(3,5),(0,6},(5,7},(3,8),(5,9},(6,10),(8,11),(8,12),(2,13),(12,15});//下标0不用
//求解结果表示

bool flag[MAx];//标记选择的活动
int Count=0;//选取的兼容活动个数

void solve()//求解最大兼容活动子集
{memset(flag,0,sizeof(flag));//初始化为false
sort(A+1,A+n+1);//A[1..n]按活动结束时间递增排序
int preend=0;//前一个兼容活动的结束时间
for (int i=1;i<=n;i++)//扫描所有活动
{ if (A[i].b>=preend)//找到一个兼容活动
{ flag[i]=true;//选择A[i]活动
preend=A[i].e;//更新preend值
}
}
}
```

有人说要按时间长短排序，但是可以给出反例。

重新想想，按时间长短排序的目的不就是想尽快结束一个活动？那么就是按结束时间来排序。结束时间早，剩下的时间不就多了吗？

并且我们可以给出结论，最优解中的至少最长的事件序列一定包含最早结束的事件。

反证法，所有的最长事件序列都不包含最早结束的事件。

任取一个事件序列，把这个最早结束的事件去掉，换成更早结束的事件，那么这个事件序列不就是包含了更早结束的事件？（因为是按事件个数而不是时间长短）

那么算法思路就出现了：选中最早结束事件，划成子问题，然后再找最早结束的事件

#### 哈夫曼树编码

数据结构P147

  

``` 
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*Huffman Tree;
typedef char ** HuffmanCode ;// 动态分配数组存储哈夫曼树编码表
void Huffmancoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) //构造哈夫曼编码
{
//w存放n个字符的权值(>0)，构造哈夫曼树HT,并求出n个字符的哈夫曼树编码HC
if (n<=1) return;
m=2*n-1;
HT=(HuffmanTree) malloc((m+1)*sizeof(HTNode))
for (p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0}
for (;i<=m;++i,++p) *p={0,0,0,0};
for (i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//从叶子到根逆向求每个字符的哈夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd =(char * )malloc (n*sizeof(char));
cd [n-1]="\0";
for (i=1;i<=n;++i){
start=n-1;
for (c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)..从叶子到根你想求编码
	if(HT[f].lchild==c) cd[--start]="0";
	else cd [--start] ="1";
HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码串到HC
}
free(cd);
}
```



```
void CreateHcode()
{ string code;code.reserve(MAx);//构造哈夫曼编码
for (int i=0;i<n;i++)//构造叶子结点i的哈夫曼编码
{ code="";
int curno=i;
int f=ht[curno].parent;
while (f!=-1)//循环到根结点
{ if (ht[f].lchild==curno)//curno为双亲f的左孩子
code=''+code;
else//curno为双亲f的右孩子
code='1'+code;
curno=f; 
f=ht[curno].parent;
}htcode[ht[i].data]=code; //得到ht[i].data字符的哈夫曼编码
}
}
//构造哈夫曼树
void CreateHTree()
{ NodeType e,e1,e2;
priority_queue<NodeType> qu;
for (int k=0;k<2*n-1;k++)//设置所有结点的指针域
ht[k].lchild=ht[k].rchild=ht[k].parent=-1;
for (int i=0;i<n;i++) //将n个结点进队qu
e.no=i; e.data=ht[i].data;
e.weight=ht[i].weight; qu.push(e);}
for (int j=n;j<2*n-1;j++)//构造哈夫曼树的n-1个非叶子结点
e1=qu.top();qu.pop(); //出队权值最小的结点e1
e2=qu.top(); qu.pop();//出队权值次小的结点e2
ht[j].weight=e1.weight+e2.weight;/构造哈夫曼树的非叶子结点j
ht[j].lchild=e1.no;
ht[j].rchild=e2.no;
ht[e1.no].parent=j;//修改e1.no的双亲为结点j
ht[e2.no].parent=j;//修改e2.no的双亲为结点j

e.no=j;//构造队列结点e
e.weight=el.weight+e2.weight;
qu.push(e);

```

 

l 最短路径问题

l 最小耗费生成树

**单源最短路径问题**

Dijstra算法

其基本思想是：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

贪心选择性质证明：

反证法 

即证明从源到u没有更短的其他路径。假设存在一条从源到u且长度比dist[u]更短的路，设这条路初次走出S之外到达顶点为x#V-S，然后徘徊于S内外若干次，最后离开达到u，如上图所示。

在这条路径上，分别记d(v,x)，d(x,u)和d(v,u)为顶点V到顶点x，顶点x到顶点u和顶点V到顶点u的路长，那么
$dist[x]<=dist(v,x) d(v,x)+d(x,u) = d(v,u) < dist[u]$利用边权的非负性，可知d(x,u)>=0，从而推得dist[x]<dist[u]。此为矛盾。这就证明了dist[u]是从源到顶点u的最短路径长度。

```
Dijkstra(int n,int v,Type dist[],int prev [].Type **c)
{单源最短路径问题的迪杰斯特拉算法
bool s[maxint]:
for (int i= 1:i<=n:i++){
dist[i]=c[v][i];
s[i]= false;
if (dist[i]==maxint) 
prev[i] = O;
else prev[i] = v;
}
dist[v]=0; s[v]=true;
for (int i=1;i<n:i++){
int temp = maxint;
int u=v;
for (int j=1;j<=n:j++)
if ((!s[i])&&(dist[j]<temp))
{u=j;temp = dist[i];}
s[u]= true;
for(int j=1;j<=n;j++)
if((!s[j])&&(c[u][j]<maxint))
{Type newdist = dist[u] +c[u][j]:
if (newdist < dist[j]){dist[j]=newdist;prev[i]=u;}
}
```

C[i]\[j]表示边(i,j)的权，n是顶点个数，V表示源，dist[i]表示当前从源到顶点i的最短特殊路径长度

思考:本算法只是给出了从源顶点到其他顶点间的最短路径长度，并没有记录相应的最短路径。该如何修改才可以记录相应的最短路径?

l Bellman-Ford算法

l 有向无回路图中的单源最短路径算法

l Dijkstra算法

l 每对顶点间的最短路径算法基本概念

l Floyd算法

**搬桌子**

[Problem - 1050](http://acm.hdu.edu.cn/showproblem.php?pid=1050)

是不是可以参考活动安排的思路？不就错误了吗？

![image-20251206221634912](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251206221634912.png)

有重叠，重叠得越多，搬运的次数越多。所以怎么减少重叠？

找最早开始的行吗？确保最高的重叠度-1。

也可以想象成数组，路过的位置+1，看最高搬了几次。

```
#include <iostream>
using namespace std;
int main(){ int t.i.j.N,P[200];
int s.d.temp.k.min;
cin>>t;
for(i=0:i<t:i++)
{for(j=0:j<200:j++)
	P[j]=0;
cin>>N;
for(j=0:j<N:j++)
{cin>>s>>d;s=(s-1)/2;d=(d-1)/2;
if(s>d)
{temp=s;s=d;d=temp;}
for(k=s:k<=d:k++)
P[k]++;}
min=-l;
for(j=0:j<200:j++)
if(P[j]>min)
min=P[j];cout<<min*l0<<endl;
}
return 0;
}
```

**田忌赛马**

各有N匹马

先找到第一个能赢的（即田忌的第一匹马大于对手的第一匹马的）

或者说如果比不过，用最差的马跟你比。

，然后继续找

最快的马速度相同怎么办？

比较最慢的马，如果最慢的马快于对手的马，则最慢的马比，否则用最慢的马去比对手最快的马（也就是当前比较的马）。

1. **不是简单匹配第一个能赢的**
2. **要同时考虑最快和最慢的马**
3. **能赢就赢，必要时用最差的马消耗对方最好的马**
4. **目标是整体赢的场次最多，不是每一场都赢**

同样地，如果最快的马和最慢的马速度都相同，就用最慢的马去比对手最快的马。

找到贪心问题的本质





[Problem - 1800](http://acm.hdu.edu.cn/showproblem.php?pid=1800)

求众数。类似于桶排序。

但是数字有100位，怎么办？——用字符串去比较。



去掉s位，留下的数字最小？

比较最高位和最高-1位，如果最高位大于-1位，去掉最高位。

如果不是，则继续比较最高-1位和最高-2位，如果-1位更高，去掉。

直到最后，去掉最后一个。

129，去9；219，去2；



**青蛙的邻居问题（可图性判定，根据度来判定是否可形成图）**

Havel-Hakimi定理

如果全变成0，则可图。

最小生成树，也是贪心

收银员

**币值问题**

币数量越少越好。

[Problem - 1007](http://acm.hdu.edu.cn/showproblem.php?pid=1007)

平面上有10万个点，问最近的那一对点的距离

详见《算法导论》

贪心算法的常见操作：排序；选择排序和堆排序