算法设计与分析（贪心法）

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…

文章目录

• 一、贪心法的基本思想
• 二、贪心法的基本要素
• • 1.最优子结构性质
  • 2.贪心选择性质
• 三、贪心法的解题步骤及算法设计模式
• • 1、步骤：
  • 2、设计模式
• 四、会场安排问题
• 五、最优装载问题
• 总结

一、贪心法的基本思想

贪心法是一种稳扎稳打的算法，他从问题的摸一个初始解出发，在每一个阶段都根据贪心策略来做出当前最优决策，逐步逼近给定目标，尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法终止。也可以理解为：以逐步的局部最优，达到最终的全局最优。

二、贪心法的基本要素

1.最优子结构性质

当一个问题的最优解一定包含其他子问题的最优解时，称此问题具有最优子结构性质。（一个问题能够分解成各个子问题来解决，通过各个子问题的最优解能递推到原问题的最优解，此时原问题的最优解一定包含各个子问题的最优解，这是能够采用贪心法来求解问题的关键）

在分析问题是否具有最优子结构性质时，通常先设出问题的最优解，给出子问题的解一定是最优的结论。然后，采用反证法证明“子问题的解一定时最优的”结论成立。证明思路是：设原问题的最优解导出子问题的解不是最优的，然后在这个假设下可以构造出比原问题的最优解更好的解，从而导致矛盾。

2.贪心选择性质

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最优选择使得最终的选择方案是全局最优的。其中每次所做的选择，可以依赖于以前的选择，但不依赖于将来所做的选择。

贪心选择性质所做的是一个非线性的子问题处理流程，即一个子问题并不依赖于另一个子问题，但是子问题间有严格的顺序性。

三、贪心法的解题步骤及算法设计模式

1、步骤：

• 1.分解：
  将原问题分解为若干个相互独立的阶段。

• 2.解决：
  对于每个阶段依据贪心策略进行贪心选择，求出局部的最优解。

• 3.合并：
  将各个阶段的解合并为原问题的一个可行解。

2、设计模式

Greedy(A,n)
{
    //A[0:n-1]包含n个输入，即A是问题的输入集合
    将解集合solution初始化为空;
    for(i=0;i<n;i++)                        //原问题分解为n个阶段
    {
        x=select(A);                        //依据贪心策略做贪心选择，求得局部最优解
        if(x可以包含在solution)              //判断解集合solution在加入x后是否满足约束条件
            solution=union(solution,x);    //部分局部最优解进行合并
    }
    return (解向量solution);                //n个阶段完成后，得到原问题的最优解
}

四、会场安排问题

此问题的核心思想是：每次从剩下未安排的会议中选择具有最早结束时间且不会与已安排的会议重叠的会议来安排。这样可以使下一个会议尽快开始。

1）实现活动安排问题的贪心算法。

测试数据可选用：

#include <iostream>
using namespace std;
void Select(int n, int A[],int B[], bool C[])
{
	int i, j;
	C[1] = true;
	j = 1, i = 2;
	while (i <= n)
	{
		if (A[i] > B[j]) {
			C[i] = true;
			j = i;
		}
		else {
			C[i] = false;
		}
		i++;
	}
};


int main()
{
	int A[11] = { 0,1,3,2,5,3,5,6,8,8,2 },
		B[11] = { 0,4,5,6,7,8,9,10,11,12,13 };
	bool C[11];
	Select(11, A, B, C);
	cout << "活动安排如下：" << endl;
	for (int k = 1; k <= 11; k++)
	{
		while (C[k])
		{
			cout << A[k]<<"  "<<B[k] << endl;
			break;
		}
	}
	return 0;
}

运算截图如下：

五、最优装载问题

2）实现最优装载的贪心算法。

测试数据可选用：

假设轮船限重12kg

#include "TanXin2.h"
#include<iostream>
using namespace std;
#define Max 10
typedef struct {
	int *elem;
	int length;
}SqList;

int InitList(SqList &L)//构造并初始化
{
	L.elem = new int[Max];
	if (!L.elem) return 0;
	L.length = 0;
	return 1;
}

void InputList(SqList &L,SqList &LB, int n)
{
	L.length = 0;
	if (n<0 || n>Max) return;
	cout << "请输入顺序表" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> L.elem[i];
		L.length++;
	}
	for (int j = 0; j < n; j++)
	{
		LB.elem[j] = L.elem[j];
		LB.length++;
	}
}

void OutputList(SqList L)
{
	for (int i = 0; i < L.length; i++)
	{
		cout << L.elem[i] << " ";

	}
}

void Compare(SqList &L)//冒泡排序
{
	int i, j, e;
	for (i = 1; i <= L.length; i++)
	{
		for (j = 0; j < L.length - i; j++)
		{
			if (L.elem[j] > L.elem[j + 1])
			{
				e = L.elem[j];
				L.elem[j] = L.elem[j + 1];
				L.elem[j + 1] = e;
			}
		}
	}
}

int LocateElem(SqList L, int e)//查找数据是否在顺序表内
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e) return i + 1;//查找成功，返回序号i+1
	}
	return 0;//查找失败，返回0
}

void Select(SqList &L,SqList &LB,int m)
{
	int sum = 0;
	for (int i = 0; i < L.length; i++)
	{
		if ((sum + L.elem[i]) < m)
		{
			sum += L.elem[i];
			cout<< LocateElem(LB, L.elem[i]) <<"  "<< L.elem[i] << endl;
		}
		else {
			break;
		}
	}
}

int main()
{
	int n = 5,m=12;
	SqList LA,LB;
	InitList(LA);
	InitList(LB);
	InputList(LA,LB,n);
	Compare(LA);
	cout << "所选择的为：" << endl;
	Select(LA,LB,m);

}

代码运行截图如下：

总结

以上就是算法设计与分析（贪心法）的相关知识点，希望对你有所帮助。
积跬步以至千里，积怠惰以至深渊。时代在这跟着你一起努力哦！