[数据结构与算法]Acm入门四:贪心算法

在求解最优解过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次贪心选择,最终得出整个问题的最优解,这就是贪心算法。

从贪心算法的定义可以看出,贪心算法不是从整体上考虑问题,它所做出的选择,只是在某种意义上的局部最优解,而由问题自身的特性决定了该题可以运用贪心算法得到最优解。

如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。

目录

1.活动安排问题

2.贪心算法的理论基础

2.1 贪心选择性质

2.2最优子结构性质

2.3贪心算法的求解过程

3.背包问题

4.最优装载问题

5.单源最短路径

一:活动安排问题

• 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法求解的很好例子
• 该问题要求高效的安排一系列争用某公共资源的活动
• 贪心算法提供了一个简单、漂亮的方法使得更多的公共资源兼容地使用公共资源

思路?

• ?按活动结束时间升序排序
• 比较排序因子

bool cmp(const action &a,const action &b)
{
if(a.f<=b.f)return true;
return false;
}

• 使用标准库(下标0未用)

sort(a+1,a+n+1,cmp);

算法1:

//形参数组b来记录被选中的活动
void GreedySekector(int n,action a[],bool b[])
{
b[1] = true; //第一个活动是必选的
//记录最近一次加入到集合b中的活动
int preEnd = 1;
for(int i = 2;i<=n;i++)
if(a[i].s>=a[preEnd].f)
{
b[i] = true;
preEnd = i;
}
}

活动安排问题的证明

贪心选择性质证明:

设E={1,2,......,n}为所给活动集合。由于E中活动按结束时间的非减序排列,故活动1具有最早的完成时间。

首先证明活动安排问题有一个最优解以贪心选择开始,即该最优解包含活动1。

A属于E是所给问题的最优解,且A活动也是按结束时间非减序排列,A中第一个活动是k,若k=1.则A就是一个贪心选择开始的最优解。

若k＞1,设B={A-{k}U{1}},由于f1<=fk,且A中活动是相容的,故B中的活动也是相容的。又由于B中活动个数与A中活动个数相同,且A是最优的,故B也是最优的。也就是说,B是一个以贪心选择活动为1开始的最优安排。

因此,我们证明了总存在一个贪心选择开始的最优活动安排。

最优子结构性质证明:?

若A是原问题的一个最优解,则A'=A-{1}是活动问题E'={i∈E:si>f1}的一个最优解。

事实上,如果我们能找到一个E'的一个解B',它包含比A'更多的活动,则将活动1加入到B'中将产生E的一个解B,它包含比A更多的活动。这与A的最优性矛盾。

因此,每一步所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题

例题:洛谷P1223排队接水

排队接水 - 洛谷

?

题目描述

有?nn?个人在一个水龙头前排队接水，假如每个人接水的时间为?T_iTi?，请编程找出这?nn?个人排队的一种顺序，使得?nn?个人的平均等待时间最小。

输入格式

第一行为一个整数?nn。

第二行?nn?个整数，第?ii?个整数?T_iTi??表示第?ii?个人的等待时间?T_iTi?。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

输入输出样例

输入 #1复制

10 
56 12 1 99 1000 234 33 55 99 812

输出 #1复制

3 2 7 8 1 4 9 6 10 5
291.90

说明/提示

n \leq 1000,t_i \leq 10^6n≤1000,ti?≤106，不保证?t_iti??不重复。

当?t_iti??重复时，按照输入顺序即可（sort 是可以的）

思路

让节水时间短的先接水

A和B两个同学,A同学节水时间a,B同学节水时间b

A先接水,总节水时间t1=a+(a+b)=2a+b;

B先节水,总节水时间t2=b+(b+a)=a+2b;

t1-t2=a-b;

当a＜b时,t1<t2;A先接水

当a > b时,t1>t2;B先节水;

第i个人节水,对结果的贡献时ti-(n-i)

本代码不能AC

#include"iostream"
#include"cstdio"
#include"algorithm"
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f;
const double pi = 3.1415926535897932384626;
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9')
	{
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (ch > '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();

	}

	return x * f;
}

const int maxn = 1e3 + 5;
ll n;
struct people {
	ll t, idx;

}p[maxn];
bool cmp(const people &a, const people &b) {
	if (a.t == b.t)return a.idx < b.idx;
	return a.t < b.t;

}

int main() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		p[i].t = read();
		p[i].idx = i;

	}
	sort(p + 1, p + n + 1, cmp);
	double ans = 0.0;
	for (int i = 1; i <= n; ++i) {
		printf("%lld%c", p[i].idx, i == n ? '\n' : ' ');
		ans += p[i].t * (n - i);
		printf("%.2f\n", ans / 1.0 / n);
	}
	return 0;
}

明天继续写