【精选】算法设计与分析（第七章贪心法）

命运之光

发布于 2024-03-20 13:55:19

950

发布于 2024-03-20 13:55:19

文章被收录于专栏：我在本科期间写的文章

前言

总结算法设计与分析课程期末必记知识点。

第七章贪心法

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。也就是说，贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做出这个选择后产生的相应子问题的解。它是贪心法可行的第一个基本要素，也是贪心算法与后面介绍的动态规划算法的主要区别。

2、最优子结构性质

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。问题的最优子结构性质是该间题可用动态规划算法或贪心法求解的关键特征。

3、贪心法的一般求解过程

用贪心法求解问题的基本思路如下： (1)建立数学模型来描述问题 (2)把求解的问题分成若干个子问题 (3)对每一个子问题求解，得到子问题的局部最优解 (4)把子问题的局部最优解合成原来解问题的一个解。

4、求解最大兼容活动子集

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值
		}
	}
}

5、求解最大兼容活动子集个数

void solve()//求解最大兼容活动子集个数
{
	sort(A + 1, A + n + 1);//A[1..n]按指定方式排序
	memset(ans, 0, sizeof(ans));//初始化为0
	int num = 1;//畜栏编号
	for (int i = 1; i <= n; i++)//i、j均为排序后的下标
	{
		if (ans[i] == 0)//第i头牛还没有安排畜栏
		{
			ans[i] = num;//第i头牛安排畜栏
			int preend = A[i].e;//前一个兼容活动的结束时间
			for (int j = i + 1; j <= n; j++)//查找一个最大兼容活动子集
			{
				if (A[i].b > preend && ans[j] == 0)
				{
					ans[j] = num;//将兼容活动子集中的活动安排在num畜栏中
					preend = A[j].e;//更新结束时间
				}
			}
			num++;//查找下一个最大兼容活动子集，num增1
		}
	}
}

6、求解背包问题并返回总价值

void Knap()//求解背包问题并返回总价值
{
	V = 0;//V初始化为0
	double weight = W;//背包中能装入的余下重量
	memset(x, 0, sizeof(x));//初始化x向量
	int i = 1;
	while (A[i].w < weight)//物品i能够全部装入时循环
	{
		x[i] = 1;//装入物品i
		weight -= A[i].w;//减少背包中能装入的余下重量
		V += A[i].v;//累计总价值
		i++;//继续循环
	}
	if (weight > 0)//余下重量大于0
	{
		x[i] = weight / A[i].w;//将物品i的一部分装入
		V += x[i] * A[i].v;//累计总价值
	}
}

7、田忌赛马

#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX 1001
//问题描述
int n;
int a[MAX];
int b[MAX];
//求解结果表示
int ans;	//田忌获得的最多硬币数
void solve()//求解算法
{
	sort(a, a + n);//对a递增排序
	sort(b, b + n);//对b递增排序
	ans = 0;
	int lefta = 0, leftb = 0;
	int righta = n - 1, rightb = n - 1;
	while (lefta<righta)
	{
		if (a[righta] > b[rightb]) {
			ans += 200;
			righta--;
			rightb--;
		}
		else if (a[righta] < b[rightb])//田忌最快的马比齐威王最快的马慢
		{
			ans -= 200;//选择田忌最慢的马与齐威王最快的马比赛
			lefta++;
			rightb--;
		}
		else           //田忌最快的马与齐威王最快的马的速度相同
		{
			if (a[lefta] > b[leftb])//田忌最慢的马比齐威王最慢的马快，两者比赛
			{
				ans += 200;
				lefta++;
				leftb++;
			}
			else
			{
				if (a[lefta] < b[rightb])//否则用田忌最慢的马与齐威王最快的马比赛
					ans -= 200;
				lefta++;
				rightb--;
			}
		}
	}
}