• 算法入门教程（五、贪心）

    目录

    前面教程汇总

    第一讲

    算法入门教程（一、模拟）

    第二讲

    算法入门教程（二、枚举）

    第三讲

    算法入门教程（三、递推与递归）

    第四讲

    算法入门教程（四、分治）

    贪心

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

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

    贪心算法基础

    贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下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
    • 2
    样例输出 #1
    3 2 7 8 1 4 9 6 10 5
291.90

    • 1
    • 2

    提示

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    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.

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    例题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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    样例输出 #1
    4

    • 1

    提示

    对于 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
#include 
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;
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    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.

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    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)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

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

  • 相关阅读:
    SpringBoot连接MySql主从配置 读写分离
    【Django开发】0到1开发美多shop项目：短信验证码和RabbitMQ。全md文档笔记（附代码 文档）
    chatgpt
    从 min 到 max 的随机数
    HTML 样式-CSS
    【计算机网络】75 张图详解：网络设备、网络地址规划、静态路由（万字长文）
    BP神经网络需要训练的参数,bp神经网络建模步骤
    react经验14:动态修改第三方组件的样式
    VPS与云主机指南：了解五个主要区别
    UWB PDOA brief introduction
  • 原文地址：https://blog.csdn.net/weixin_59197425/article/details/126283132