贪心算法

埃及分数

把一个真分数表示为最少的埃及分数之和的形式

令真分数为A/B，A/B的整数部分为C，余数为D，埃及分数字母为E，有：

策略一

从最大的一个埃及分数即1/2开始试，当A/B > 1/E，则A/B-1/E，E++，继续判断尝试。

策略二

从最接近真分数的一个埃及分数开始，然后A/B = A/B - 1/E(离A/B最近的埃及分数)，然后再求最接近A/B的埃及分数。

#include <iostream>
using namespace std;

int CommFactor(int A, int B);
int EgyptScore(int A, int B);

int main() {
	int A=9;
	int B = 10;
	EgyptScore(A, B);
}

int EgyptScore(int A, int B) {
	int E, F;
	while (true) {
		E = B / A + 1;
		A = A * E - B;
		B = E * B;
		F = CommFactor(A, B);
		A = A / F;
		B = B / F;
		if (A ==1) {
      //返回最后一个埃及分数的分母
			return E;
		}
	}
}
/*求最大公约数*/
int CommFactor(int A,int B) {
	int a, b, temp;
	a = A;
	b = B;
	if (a < b) {
		temp = a;
		a = b;
		b = temp;

	}
	while (a%b != 0) {
		temp = a % b;
		a = b;
		b = temp;
	}
	return temp;
}

B=A*C+D => B/A=C+D/A<C+1,则：

A/B>1/(C+1)，故：

1/(C+1) = 1/E为A/B的最大埃及分数

A/B=C,1/(C+1),则：

E=B/A+1

A/B-1/E=A/B-1/E : *AE/B*E-B/B*E=A*E-B/B*E,故:

A=A*E-B ,B=B*E

图问题中的贪心法

TSP问题

最近顶点策略

如图，C矩阵中代表的是两点之间的距离，无穷代表对应的两点没有连线，如：C14=2就指第一行的第四列的值为2即点1到点4的距离为2。

解题思路：

P表示要走的边的集合，故P=n-1，V表示所有点的集合，选定一个起点w，判断出一个与该点距离最近的v点，令u=w（此时第一个点是起点），故Cuv便是起点到下一个点的最短距离

最短链接策略

连接距离最短的两点，注意要满足这两点没有被连过且出发点连接相应点后不再连接其它点

解题思路：

u和v在P中不连通即u和v两点还未连接过，不产生分支指即u连接了v后u就不能连接过其它点的边

时间复杂度：
O(n^2)
O(nlog2n)

图着色问题

解题思路：

1. 用颜色1着色
   (1) A着色1，无冲突
   (2) BC着色1，与A冲突
   (3) D着色1，无冲突
   (4) E着色1，与D冲突
2. 用颜色2着色
   (1) AD已着色
   (2) B着色2，无冲突
   (3) CE着色2，与B冲突
3. 用颜色3着色
   (1) ABD已着色
   (2) C着色3，无冲突
   (3) E着色3，与C冲突
4. E着色4，无冲突

时间复杂度：
O(k×n)，k为颜色数；n为结点数

最小生成树

Prime算法

基本思路：
在带权连通图中V是包含所有顶点的集合， U已经在最小生成树中的节点，从图中任意某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树。

适用于稠密图

Kruskal算法

基本思路：
将每个顶点放入其自身的数据集合中。然后，按照权值的升序来选择边。当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，则产生回路，就移动到下一条边。重复这个过程直到所有的边都探查过。

适用于稀疏图

组合问题中的贪心法

背包问题

0/1背包：物品不可拆分

部分背包：物品可以拆分

策略一

先放价值最高的物品

策略二

先放容量最小的物品

策略三

先放单位价值最高的物品

eg:

给定5个物品，其重量分别是（2,2,6,5,4），价值分别为（6, 3, 5, 4, 6），背包容量为10. 用贪心法求解该背包问题的最优解

解题过程：

程序实现：

int Bag(int w[], int v[], int C, int n) {
	//单位重量
	double x[50] = { 0 };
	int maxValue = 0;
	int i = 0;
	for (; x[i] < C; i++) {
		//整个物品
		x[i] = 1;
		maxValue += v[i];
		C -= w[i];
	}
	//剩余不完整或没有物品
	x[i] = (double)C / w[i];
	maxValue += x[i] * v[i];
	return maxValue;
}

若为01背包这不考虑物品i装入一部分的情况

时间复杂度：

O(nlog2n)