算法入门教程(五、贪心)

发布于:2023-01-22 ⋅ 阅读:(13) ⋅ 点赞:(0) ⋅ 评论:(0)

前面教程汇总

第一讲

算法入门教程(一、模拟)

第二讲

算法入门教程(二、枚举)

第三讲

算法入门教程(三、递推与递归)

第四讲

算法入门教程(四、分治)

贪心

贪心算法也被称为贪婪算法,它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题,仅仅是在某种意义上的局部最优求解。

虽然贪心算法并不能得到所有问题的整体最优解,但是面对范围相当广泛的许多问题时,能产生整体最优解或者是整体最优解的近似解。由此可见,贪心算法只是追求某个范围内的最优,可以称之为“温柔的贪婪”。

贪心算法基础

贪心算法从问题的某一个初始解出发,逐步逼近给定的目标,以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时,就停止算法,给出一个近似解。由贪心算法的特点和思路可看出,贪心算法存在以下3个问题。

  • 不能保证最后的解是最优的。
  • 不能用来求最大或最小解问题。
  • 只能求满足某些约束条件的可行解的范围。

贪心算法的基本思路如下。

  1. 建立数学模型来描述问题。
  2. 把求解的问题分成若干个子问题。
  3. 对每一子问题求解,得到子问题的局部最优解。
  4. 把子问题的局部最优解合并成原来解问题的一个解。

实现该算法的基本过程如下。

  1. 从问题的某一初始解出发。
  2. while能向给定总目标前进一步。
  3. 求出可行解的一个解元素。
  4. 由所有解元素组合成问题的一个可行解。

例题与解

例题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 n1000,ti106,不保证 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+n1 行:每行两个数 苹果高度 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 n5000, a ≤ 50 a\leq 50 a50, b ≤ 200 b\leq 200 b200, s ≤ 1000 s\leq 1000 s1000, x i ≤ 280 x_i\leq 280 xi280, y i ≤ 100 y_i\leq 100 yi100

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

本文完。关于贪心算法的题还有很多,可以在洛谷上刷。需要注意的是,贪心算法没有一个固定的代码框架。本文由于代码有一些已经加了注释,所以就不在文章里说明了,如果不懂,欢迎在评论区留言。