14.贪心算法网站首页 学无止境

14.贪心算法

风中的微尘 2024-06-17 10:14:45

简介14.贪心算法

一、算法内容

1.简介

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择，而不考虑后续可能造成的影响。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

在贪心算法的应用当中，往往都会和排序联系起来，所以想要熟练使用贪心算法则必须首先能够熟练地应用排序。而由于贪心算法采取的是局部最优策略，故如果使用贪心算法之前往往需要证明算法的正确性，即证明在此题目/事件中，在每一步采取局部最优策略会得到整体最优的结果。

2.对比与联系

与此算法相对应的是后续我们会学到的动态规划，在动态规划中我们则必须要考虑一个选择对后续的影响。

贪心算法的应用非常广泛，很多其他的算法都需要贪心算法来作为基础。例如：哈夫曼编码、 $Kr u s ka l$ 算法、 $P r im$ 算法、 $A^*$ 算法等等。所以学好贪心算法是非常重要。

二、实例分析

1.最简单的例子

下面我们将以洛谷上的题目P1208为例，讲解贪心算法的最简单的使用方式。

（1）题目大意

公司需要收购一定量的牛奶
每一个奶农能卖出的牛奶的量和价格都不同
公司希望能以最少的钱买到足够量的牛奶

（2）题目分析

显然按照题目意思，我们只需要将牛奶价格排序好，然后从价格低的开始买，如果此价格的牛奶已经没了，那么才购买价格更高的牛奶，一直买到满足公司收购的量为止即可。

本题目的贪心非常浅显易懂，这里不再给出证明。

（3）正解程序

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long ll;
const ll maxn=5010;
ll n,m,ans=0;
struct node
{
    ll per,num;
}farmer[maxn];
bool cmp(node x,node y)
{
    if(x.per!=y.per)
		return x.per<y.per;
    else
		return x.num>y.num;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++)
		scanf("%lld%lld",&farmer[i].per,&farmer[i].num);
	sort(farmer+1,farmer+1+m,cmp);
	ll pos=1;
	while(n)
	{
		if(farmer[pos].num!=0)
		{
			farmer[pos].num--;
			ans+=farmer[pos].per;
			n--;
        }
		else
			pos++;
	}
	printf("%lld
",ans);
	
	return 0;
}

2.稍微复杂一点的例子

下面我们将以洛谷上的题目P1094为例，讲解贪心算法的进一步应用，并给出证明的思路。

（1）题目大意

有一组物品需要进行分组，每个物品都有一个价格
希望保证每一组的价格总和小于某一固定值的情况下，使得分组数尽量小
每一组最多包含两个物品

（2）题目分析

首先我们能够想到，要使分组数尽可能小，那么一定是尽量两两组合
所以我们很容易能够想到一个贪心思路，那就是将物品按价格从小到大排序，然后尽量用价格小的和价格大的进行组合。
可以提前说明的是，这个贪心思路是正确的，然而问题并没有完全解决，为什么这样组合之后就能使得最后的分组数最小呢？

（3）贪心证明

根据我们前面所讲到的点，将使用反证法证明
设价格总和上限为 $X$ ，现有四个物品的价格为 $v_a,v_b,v_c,v_d$ ，按从小到大排序
若 $v_a+v_dleq X,v_b+v_cleq X$ ，此为贪心法得到的分组，最少分为两组。下面改变组合方式，因为 $v_a+v_cleq X$ 显然成立，所以仅考虑另一组的情况。
- 若 $v_b+v_dleq X$ ，那么可以分为两组
- 若 $v_b+v_dleq X$ ，那么仅能分为一组。因为 $v_aleq v_b$ ，所以此处情况完全可能出现。
若 $v_a+v_d> X$ 则无论如何都只能分为一组
若 $v_a+v_dleq X,v_b+v_c> X$ 。下面考虑 $v_a+v_c,v_b+c_d$ 这一种组合方式，显然 $v_b+v_d>X$ ，所以无论怎么分仍然只有一组。
可以看到，非贪心的情况有可能导致答案数变少。例如 $v_a=1,v_b=5,v_c=6,v_d=8,X=11$

（4）正解程序

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long ll;
const ll maxn=1000010;
ll num[maxn],ans;
int main()
{
	ll n,w;
    scanf("%lld%lld",&w,&n);
    for(ll i=0;i<n;i++)
        scanf("%lld",&num[i]);
    sort(num,num+n);
    ll z=0,y=n-1;
    while(z<=y)
	{
		if(num[z]+num[y]<=w)
		{
			ans++;
			z++;
			y--;
		}
		else
		{
			y--;
			ans++;
		}
	}
	printf("%lld
",ans);
	
	return 0;
}