贪心算法

Method #

基本思想 #

贪心算法基本思想

贪心算法是一个分阶段决策过程,在每个局部阶段,贪心法都做出一个当前 最优的局部决策,并期望通过每次所做的局部最优决策产生一个全局最优解。

贪心算法类似于分治算法和动态规划,也是一种基于子问题思想的策略。

贪心算法求解步骤

  1. 分解,将原问题求解过程划分为连续的若干个决策阶段
  2. 决策,在每一个阶段依据贪心策略进行贪心决策,得到局部的最优解,并缩小待求解问题的规模
  3. 合并,将各个阶段的局部解合并为原问题的一个全局最优解
Greedy(C) { // C是问题的输入集合即候选集合
	S = {}; // 初始解集合为空集
	while (not Solution(S)) { // 集合S没有构成问题的一个可行解
	x = Select(C); // 在候选集合C中做贪心决策
	S = S + {x};
	C = C - {Collection(x)}; // 减去一个与x关联的集合,缩小问题规模
	}
	return S;
}

正确性证明 #

数学归纳法

交换论证法

交换论证法 (Exchange Argument ): 从任意一个最优解出发,经过不断用新的要素 (符合贪心准则) 替换解中的原有要素来改变这个解。通过有限步替换,把这个最优解改造成贪心算法的解。如果替换过程中的每一步能保证解的最优值不发生变化,则证明了贪心算法的解也是最优的。

具体步骤:

  1. 给出贪心算法解 A 的描述
  2. 假设 O 是一个最优算法解 (如果有多个则随机选)
  3. 找出 O 和 A 中的一个不同要素 (可以是一个元素在 O 不在 A 或者反之,或者是一个子序列的顺序 A 和 O 不一样)
  4. 交换 (Exchange)*上述不同的要素,然后论证 (Argue) 得到的新解 O 不比 O 差
  5. 论证类似的不同要素为有限个 (多项式量级),然后交换有限次 (多项式量级) 可以消除所有的不同,同时保证了算法的质量不比 O 差

e.g.s #

活动安排问题 #

假设某社团某一天要组织𝑛个活动𝐸={1,2,⋯,𝑛} ,其中每个活动都要求使用同一礼堂,而且
在同一时间内只有一个活动能使用这个礼堂。每个活动𝑖都有一个要求使用礼堂的起始时间𝑠𝑖
和结束时间 𝑓 ,且有𝑠 < 𝑓 。如果选择了活动𝑖,则它在半开时间区间[𝑠 , 𝑓 ) 内占用资源。若区间[𝒔𝒊, 𝒇𝒊) 与区间[𝒔𝒋, 𝒇𝒋) 不相交,则称活动𝐢与活动𝐣是相容的。现在给定𝑛个活动的开始时 间和结束时间,请设计一个活动安排方案,使得安排的相容活动数目最多。
int greedyEventSchedule(int n,int *timeStart,int *timeFinish) { 
	int i,j,selected,ans=0; //冒泡排序,使得活动按结束时间升序排列
	for(i=0; i<n; i++)
		for(j=0; j+1<n; j++) if(timeFinish[j]>timeFinish[j+1]) {
			swap(timeFinish[j],timeFinish[j+1]);
			swap(timeStart[j],timeStart[j+1]); //注意开始时间也需一致移动 
		}
	ans = 1;
	selected = 0; //选择第一个活动
	for(i=1; i<n; i++)
		if(timeStart[i]>= timeFinish[selected]) {
			selected = i; //选择相容的最早结束活动
			ans++; 
		}
	return ans; 
}

算法正确性证明

小数背包问题 #

问题描述:给定𝑛种物品和一个背包。物品𝑖的重量是𝑊𝑖,其价值为𝑉𝑖,背包的容量为C,应如何 选择装入背包的物品使得装入背包中物品的总价值最大? 这里,在选择物品𝑖装入背包时,可以选 择物品𝑖的一部分,而不一定要全部装入背包。
输入:多组测试数据。每组测试包括三行:第一行输入物品的总数𝑛(𝑛 < 1000)和背包的容量 𝐶(𝐶 < 1000)。第二行输入𝑛个整数,表示物品的重量。第三行输入物品的价值。 输出:输出装入背包的总价值,每组测试数据输出一行。
输入样例:
3 50
10 20 30 60 100 120
输出样例:
240

#include<stdio.h> #include<algorithm> using namespace std; #defineMaxItems 1000 
struct item{
	int weight;
	int value;
	bool operator <(const item& bb) const { //定义比较函数(小于号)
		return value/(1.0*weight) > (1.0*bb.value)/bb.weight; //为什么乘以1.0?
	}
}; //定义物品的结构体
double greedyKnapsack(int n,int capacity,item* itemSet) {
	double ans = 0; 
	sort(itemSet,itemSet+n); //STL中的快速排序算法
	for(int i=0; i<n; i++)
		if(itemSet[i].weight <= capacity){
			ans += itemSet[i].value;//选择单价最大的物品 capacity -= itemSet[i].weight;
			capacity-=itemSet[i].weight;
		} else {
			ans += capacity*(itemSet[i].value*1.0)/itemSet[i].weight;//最后一个物品只能装部分 
			break;
		}
	return ans;
}

在这段代码中,乘以 1.0 主要是为了确保在进行除法运算时,使用浮点数而不是整数。在 C++ 中,如果两个整数进行除法运算,结果会被截断为整数部分,这可能导致不准确的比较结果。

通过乘以 1.0,将其中一个操作数转换为浮点数,整个表达式就会被当作浮点数运算,确保得到的结果是浮点数而不是整数。这样可以避免由于整数截断而导致的错误比较。

字符编码 #

一个包含100,000个字符的文件,各字符出现频率不同,如下表所示。请设 计一个编码算法,把每一个字符转换为二进制编码。
不同的字符

二元前缀码 在一个字符集的编码表 (每一个编码都表示为 0-1 字符串) 中,如果任何一个字符编码 都不是其它字符编码的前缀,则该编码称为二元前缀码。

二元前缀码的存储通常采用二叉树结构,令字符保存在叶节点,则该字符的前缀码对 应根到该叶节点的一条路径。规定每个节点通向左儿子的边记为 0,通向右儿子的边 记为 1,则根到叶节点的路径则可以转换为一个 0-1 串,映射为二元前缀码。

一个字符集可以构造多个二元前缀码。

哈夫曼编码

哈夫曼编码算法的贪心策略是: 给频率高的字符较短的代码; 频率低的字符较长的代码

把编码映射成二叉树,则其贪心策略可表述为: 把频率高的字符分配给靠近根结点 (较浅) 的叶结点,把频率低的字符放置在远离根结点 (较深) 的叶结点

自底向上构造二叉编码树,由森林不断合并得到一棵二叉树

struct cmp {
	bool operator () (const int &x,const int &y) {
		return x > y; 
	}
}; //定义优先队列需要的比较函数

double haffmanCoding(int n, int* freq) {
  int i, total = 0, sumFreq = 0, jointFreq;
  priority_queue<int, vector<int>, cmp> heap;  // 优先队列,最小值优先
  for(int i=0;i<n;i++){
	  total += freq[i];
	  heap.push(freq[i]);
  }
  while (heap.size() > 1) {  // 循环选择队列中频次最少的两个元素合并
    jointFreq = 0;           // 合并后结点的频次
    for (i = 0; i < 2; i++) {  // 删除频次最少的两元素
      jointFreq += heap.top();
      heap.pop();
    }
    sumFreq += jointFreq;
    heap.push(jointFreq);  // 优先队列中插入合并结点
  }
  return sumFreq / (1.0 * total);  // 返回平均码长
}

单源最短路径问题 #

给定带权有向图G = (V, E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称 为源。现在要计算从源到所有其它各顶点的最短路径长度,假设从源可以到达任何一个顶点。 这里路径的长度是指路径上各边权之和。这个问题通常称为单源最短路径问题。

从源到任意顶点的最短路径具有类似于最优子结构性质的特征: 即最短路径的子 路径也是源到相应顶点的最短路径。

Dijkstra 算法

Dijkstra 算法的贪心策略是选择集合𝐕 − 𝐒中受限路径长度最短的顶点,并把相应顶点加 入 𝑆 中,相应地最短路径树 𝑇 也增加一条边。

#include <iostream>
#define INF 0x03F3F3F3F
#define MaxV 100
int preV[MaxV]; // 最短路径树中的前驱结点信息表
int visited[MaxV]; // 结点是否加入S的标记表,0 是未加入,1 为已加入

void Dijkstra(int linkMatrix[][MaxV], int lowLR[MaxV], int numV, int beginV) {
    int i, j, min, newCost;
    memset(visited, 0, sizeof(visited)); // 初始化,所有节点未加入
    visited[beginV] = 1;

    // 开始节点 beginV加入列表中
    for (int i = 0; i < numV; i++) {
        lowLR[i] = linkMatrix[beginV][i];
        preV[i] = beginV;
    }

    // 准备正式开始Dijkstra算法流程
    lowLR[beginV] = 0;
    preV[beginV] = -1;
    int selectV = beginV;
    for (int i = 0; i < numV; i++) {
        for (int j = 0; j < numV; j++) {
            newCost = lowLR[selectV] + linkMatrix[selectV][j];
            if (visited[j] == 0 && newCost < lowLR[j]) {
                lowLR[j] = newCost;
                preV[j] = selectV;
            }
        }
        min = INF;
        // 贪心选择最短路径
        for (int j = 0; j < numV; j++) {
            if (visited[j] == 0 && lowLR[j] < min) {
                min = lowLR[j];
                selectV = j;
            }
        }
        visited[selectV] = 1;
    }
}

正确性证明

最小生成树问题 #

问题描述:设𝐺 =(𝑉,𝐸)是无向连通带权图。E中每条边(𝑣,𝑤)的权为𝐶(𝑣,𝑤)。如果𝐺的子图𝐺’是 一棵包含𝐺的所有顶点的树,则称𝐺’为𝐺的生成树。生成树上各边权的总和称为该生成树的耗费。 在G的所有生成树中,耗费最小的生成树称为G的最小生成树。请设计算法计算G的最小生成树的 权重总和。

图的生成树

定义: 如果连通图 G 的一个子图是一棵包含 G 的所有顶点的树,则该子图称为 G 的生 成树 (Spanning Tree)。

最小生成树

定义: 对于连通的带权图 G=(V, E),其生成树也是带权的,生成树 T=(V, TE) 各 边的权值总和称为该树的权 W(T), TE 表示 T 的边集,𝐶(𝑢,𝑣) 表示边 (u,v) 的权重。 权最小的生成树称为 G 的最小生成树 (Minimum Spanning Tree, MST)。

Prim 算法

#include <iostream>
#define INF 0x03F3F3F3F
#define MaxV 1000

int prim(int linkMatrix[][MaxV], int numV) {
    int visited[MaxV] = {0};
    int lowCost[MaxV], closet[MaxV];
    int i, k;
    int min, costMST = 0;
    visited[0] = 1;
    closet[0] = -1;

    for (int i = 0; i < numV; i++) {
        lowCost[i] = linkMatrix[0][i];
        closet[i] = 0;
    }

    for (int i = 0; i < numV - 1; i++) {
        min = INF;
        int selectV = 0;
        for (int k = 0; k < numV; k++) {
            if (!visited[k] && lowCost[k] < min) {
                min = lowCost[k];
                selectV = k;
            }
        }
        costMST += min;
        visited[selectV] = 1;
        for (int k = 1; k < numV; k++) {
            if (!visited[k] && linkMatrix[selectV][k] < lowCost[k]) {
                lowCost[k] = linkMatrix[selectV][k];
                closet[k] = selectV;
            }
        }
    }
    return costMST;
}

正确性证明

并查集 #

并查集 (Disjoint set 或者 Union-find set) 是一种树型的数据结构,常用于处理一些不相交集 合 (Disjoint Sets) 的合并及查询问题。它包含两种基本操作:

查询

合并

并查集优化策略一——路径压缩

路径压缩是一种在执行“查询”时扁平化树结构的方法,为后续查询操作加速。

并查集优化策略二——按秩合并

按秩合并即总是将更浅的树连接至更深的树上,避免增加合并树的秩

Kruskal 算法 #

给定无向带权图𝐺=(𝑉,𝐸),𝑉={1,2,…,𝑛}。设最小生成树𝑀𝑆𝑇 = (𝑉, 𝑇𝐸),该树的 初始状态为只有𝐧个顶点而无边的非连通图𝑇 = (𝑉, {} ), Kruskal 算法将这𝑛个顶点看成 是𝑛个孤立的连通分支;

贪心选择: 在边集𝐸中选择权值最小的边 (𝑖, 𝑗),如果将边 (𝑖, 𝑗) 加入 TE 中不产生回路,则 将边 (𝑖, 𝑗) 加入 TE,即用边 (𝑖, 𝑗) 将 T 中的两个连通分支合并成一个联通分支; 否则舍弃它。 循环此过程,直至所有顶点都在一个联通分支。

Kruskal 算法俗称避环法,该算法的实现关键是在加入边时避免出现环路 用并查集来实现连通分支查找和合并的相关操作

int kruskal(node juSet[MaxV], int numV, edge edgeSet[MaxE], int numE) {
    qsort(edgeSet, numE, sizeof(struct edge), cmp);
    for (int i = 0; i < numE; i++) {
        fatherX = Find_Set(edgeSet[i].x);
        fatherY = Find_Set(edgeSet[i].y);
        if (fatherX == faterY) {
            totalCost += edgeSet[i].w;
            cntW++;
        }
        if (cntE == numV - 1) {
            return totalCost;
        }
    }
    return totalCost;
}

小结 #

贪心算法的正确性证明