目录
前面教程汇总
第一讲
第二讲
第三讲
第四讲
贪心
贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。
虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。
贪心算法基础
贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3个问题。
- 不能保证最后的解是最优的。
- 不能用来求最大或最小解问题。
- 只能求满足某些约束条件的可行解的范围。
贪心算法的基本思路如下。
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的局部最优解合并成原来解问题的一个解。
实现该算法的基本过程如下。
- 从问题的某一初始解出发。
- while能向给定总目标前进一步。
- 求出可行解的一个解元素。
- 由所有解元素组合成问题的一个可行解。
例题与解
例题1：P1223 排队接水
题目描述
有 n n n 个人在一个水龙头前排队接水，假如每个人接水的时间为 T i T_i Ti，请编程找出这 n n n 个人排队的一种顺序，使得 n n n 个人的平均等待时间最小。
输入格式
第一行为一个整数 n n n。
第二行 n n n 个整数，第 i i i 个整数 T i T_i Ti 表示第 i i i 个人的等待时间 T i T_i Ti。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
样例 #1
样例输入 #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 ≤ 1000 , t i ≤ 1 0 6 n \leq 1000,t_i \leq 10^6 n≤1000,ti≤106，不保证 t i t_i ti 不重复。
当 t i t_i ti 重复时，按照输入顺序即可（sort 是可以的）
C++解
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n,t,k;
double sum,s=0; //sum总时间一定要用double型
int a[1001],b[1001]; //a数组为每个人的等待时间，b数组用来存每个人所在位置
cin>>n;
for(int i=1;i<=n;i++) //这个循环用来输入和存位置
{
cin>>a[i];
b[i]=i;
}
for(int i=1;i<=n;i++) //这个循环用来排序时间和交换位置
{
for(int j=i;j<=n;j++)
{
if(a[i]>a[j])
{
swap(a[i],a[j]);
swap(b[i],b[j]);
}
}
}
for(int i=1;i<=n;i++) //这个循环用来计算总时间
{
s+=a[i]*(n-i);
}
sum=s/n; //平均时间
for(int i=1;i<=n;i++)
{
cout<<b[i]<<" ";
}
cout<<endl;
printf("%.2f\n",sum); // 保留小数后两位输出
return 0;
}
Pascal解
var
a,b:array[0..5000]of longint;
n,i,j,t:longint;
begin
read(n);
for i:=1 to n do //读入
read(a[i]);
for i:=1 to n do
b[i]:=i;
for i:=1 to n-1 do //排序
for j:=i+1 to n do
begin
if a[i]>a[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
t:=b[i];
b[i]:=b[j];
b[j]:=t;
end;
end;
for i:=1 to n do //每个人的时间就是他的时间乘他前面的人数加一
s:=s+a[i]*(n-i);
for i:=1 to n do //输出每个人倒时间
write(b[i],' ');
writeln; //输出中要换行
write(s/n:0:2); //输出平均时间
end.
Java解
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n;
people[] a;
double sum;
while(in.hasNext()){
n=in.nextInt();
a=new people[n];
sum=0;
for(int i=0;i<n;i++) {
a[i]=new people();
a[i].time=in.nextInt();
a[i].No=i+1;
}
sort(a);
for(int i=0;i<n;i++) {
sum=(n-i-1)*a[i].time+sum;
if(i!=n-1)
System.out.print(a[i].No+" ");
}
System.out.println(a[n-1].No);
System.out.printf("%.2f",sum/n);
System.out.println();
}
in.close();
}
private static void sort(people[] a) {
int t;
for(int i=0;i<a.length;i++) {
for(int j=a.length-1;j>i;j--) {
if(a[j].time<a[j-1].time) {
t=a[j].time;
a[j].time=a[j-1].time;
a[j-1].time=t;
t=a[j].No;
a[j].No=a[j-1].No;
a[j-1].No=t;
}
}
}
}
}
class people {
int time;
int No;
}
例题2：P1478 陶陶摘苹果（升级版）
题目描述
又是一年秋季时，陶陶家的苹果树结了 n n n 个果子。陶陶又跑去摘苹果，这次他有一个 a a a 公分的椅子。当他手够不着时，他会站到椅子上再试试。
这次与 NOIP 2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 s s s 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 s < 0 s<0 s<0 之前最多能摘到多少个苹果。
现在已知 n n n 个苹果到达地上的高度 x i x_i xi，椅子的高度 a a a，陶陶手伸直的最大长度 b b b，陶陶所剩的力气 s s s，陶陶摘一个苹果需要的力气 y i y_i yi，求陶陶最多能摘到多少个苹果。
输入格式
第 1 1 1 行：两个数 苹果数 n n n，力气 s s s。
第 2 2 2 行：两个数 椅子的高度 a a a，陶陶手伸直的最大长度 b b b。
第 3 3 3 行~第 3 + n − 1 3+n-1 3+n−1 行：每行两个数 苹果高度 x i x_i xi，摘这个苹果需要的力气 y i y_i yi。
输出格式
只有一个整数，表示陶陶最多能摘到的苹果数。
样例 #1
样例输入 #1
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
样例输出 #1
4
提示
对于 100 % 100\% 100% 的数据， n ≤ 5000 n\leq 5000 n≤5000, a ≤ 50 a\leq 50 a≤50, b ≤ 200 b\leq 200 b≤200, s ≤ 1000 s\leq 1000 s≤1000, x i ≤ 280 x_i\leq 280 xi≤280, y i ≤ 100 y_i\leq 100 yi≤100。
C++解
#include<iostream>
#include<algorithm>
using namespace std;
int n,s,a,b,x_,y_,can,rest,ans;
struct apple{
int xi,yi;
}ap[50005];
int cmp(apple x,apple y){
return x.yi<y.yi;
}
int main(){
cin>>n>>s>>a>>b;
for(int i=1;i<=n;i++){
cin>>x_>>y_;
if(x_<=a+b){
can++;
ap[can].xi=x_;
ap[can].yi=y_;
}
}
sort(ap+1,ap+can+1,cmp);
rest=s;
ans=0;
for(int i=1;rest>=ap[i].yi&&i<=can;i++){
ans++;
rest-=ap[i].yi;
}
cout<<ans;
return 0;
}
Pascal解
var n,s,a,b,i,c,j,xi,yi,k,t,p:integer;
x,y:array[1..5001]of integer;
begin
readln(n,s);
readln(a,b);
c:=0;
k:=0;
p:=0;
for i:=1 to n do
begin
readln(xi,yi);
if (a+b)>=xi then
begin
k:=k+1;
y[k]:=yi;//能摘下来就把苹果数从0开始加1，然后把相应的苹果力气保存下来（因为后面根本不需要高度）
end;
end;
for i:=1 to k-1 do
for j:=1 to k-i do
if y[j]>y[j+1]then
begin
t:=y[j];
y[j]:=y[j+1];
y[j+1]:=t;//似乎是个冒泡排序~
end;
while (s>0)and(p<=k) do
begin
p:=p+1;//纯粹为给后面减力气计数
c:=c+1;//能摘下来的苹果数
s:=s-y[p];//减去相应的力气，继续
if s<0 then
c:=c-1;//如果苹果还有，力气也大于零，但是剩下的苹果需要的力气比陶陶剩下的力气要多，所以在这个程序里会多加一个，把它减掉
end;
writeln(c);
end.
Python解
#输入变量，定义变量
apple_num,total_strength = map(int,input().split())
height = sum(map(int, input().split()))
apples = []
pick_apples = count = 0
#读入苹果数据，并筛选出够得着的苹果
for i in range(apple_num) :
apple_height, apple_strength = map(int,input().split())
if apple_height <= height :
apples.append(apple_strength)
#根据每个苹果的力气大小排序
apples.sort()
while total_strength > 0:
if apples[count]<= total_strength:
pick_apples +=1
total_strength -= apples[count]
count += 1
print(pick_apples)
Java解
import java.util.Scanner;
public class P1478 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),s=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt();
Apple[] apples=new Apple[n];
int cnt=0;
for (int i = 0; i <n ; i++) {
int x=sc.nextInt(),y=sc.nextInt();
apples[i]=new Apple(x,y);
}
sort(apples);
for (int i = 0; i < n; i++) {
if(s>=apples[i].y && apples[i].x<=(a+b)){
s-=apples[i].y;
cnt++;
}
}
System.out.println(cnt);
}
static void sort(Apple[] apples)
{
for (int i = 0; i < apples.length; i++)
{
for (int j = 0; j < apples.length; j++)
{
if(apples[i].y<apples[j].y)
{
Apple apple=apples[i];
apples[i]=apples[j];
apples[j]=apple;
}
}
}
}
}
class Apple {
int x;
int y;
public Apple(int x,int y) {
this.x=x;
this.y=y;
}
}
本文完。关于贪心算法的题还有很多，可以在洛谷上刷。需要注意的是，贪心算法没有一个固定的代码框架。本文由于代码有一些已经加了注释，所以就不在文章里说明了，如果不懂，欢迎在评论区留言。