理论基础

贪心算法基本概念

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

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

贪心算法基本思路

  • 基本思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。

  • 贪心算法过程
    • 建立数学模型来描述问题；
    • 把求解的问题分成若干个子问题；
    • 对每一子问题求解，得到子问题的局部最优解；
    • 把子问题的解局部最优解合成原来解问题的一个解。

适合解决问题

l 适用问题

​ 贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

l 实现框架

从问题的某一初始解出发；

​ while （能朝给定总目标前进一步）

​ {

​ 利用可行的决策，求出可行解的一个解元素；

​ }

由所有解元素组合成问题的一个可行解；

l 贪心策略的选择

用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

贪心算法的步骤

  1. 根据题意，确定贪心策略（局部最优能够到达全局最优）

  2. 整理数据

  3. 根据策略逐个搜索，得到问题的解

  4. 输出结果

经典贪心

最优装载问题

贪心策略：先装最轻的。（不一定得到全局最优解）

有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。

算法分析

由于只关心选择的物品的最大数量（而不是最大重量，最大重量需要考虑动态规划DP），所以装重的物体没有装轻的物体划算。这里只需对n个物体按重量递增排序，依次选择每个物体直到装不下为止。

这是一种典型的贪心算法，它只顾眼前，却能得到最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,c,w[10001];//n物体个数c总重量
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	} 
	sort(w,w+n);
	int sum=0,ans=0;
	for(int i=1;i<=n;i++){
		if(sum+w[i]<=c){
			ans++;
			sum+=w[i];
		}
	}
	cout<<ans;
}

sort函数的原理

sort函数使用一种高效的排序算法（如快速排序、堆排序或内省排序）来对元素进行排序。内省排序（Introsort）是C++标准库中常用的排序算法，它结合了快速排序、堆排序和插入排序，能够在大多数情况下提供快速排序的效率，同时避免了最坏情况下的性能问题。

详解

  1. 快速排序（Quick Sort）：一种分而治之的排序算法，平均情况下具有O(n log n)的时间复杂度，但在最坏情况下会退化为O(n^2)。
  2. 堆排序（Heap Sort）：基于二叉堆的数据结构，具有O(n log n)的时间复杂度，即使在最坏情况下也能保证这个时间复杂度。
  3. 插入排序（Insertion Sort）：对于小规模数据或几乎已排好序的数据非常高效，具有O(n^2)的时间复杂度，但在小数据集时表现良好。

内省排序的工作流程如下：

  • 首先使用快速排序对数据进行排序。
  • 如果快速排序递归深度过大，可能导致最坏情况的出现，此时切换到堆排序。
  • 在排序的最后阶段，当子序列长度较小时，使用插入排序完成排序。

总结

sort(w, w+n)是一种高效、简单的方式，用于对C++数组进行排序。它利用了内省排序算法的优势，保证了大多数情况下的高效性和最坏情况下的稳定性能。通过指定数组的开始和结束指针，可以方便地对数组进行排序，并且可以通过自定义比较函数实现不同的排序规则。

一维贪心

P23004排队打水问题

有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各（1）不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？

\【算法分析】**

由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：

  1. 将输入的时间按从小到大排序；

  2. 将排序后的时间按顺序依次放入每个水龙头的队列中；

  3. 统计，输出答案。

    • 2 1

    • 5 10

\贪心策略：使前面的人等的时间最短**

【参考程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h> 
using namespace std;
int a[10005];
int s[105];
 int main(){
	int n,r,i,j=0,minx=0;
	scanf("%d %d",&n,&r); 
	for(i=0;i<n;i++)	{
		scanf("%d",&a[i]);
	}	
	sort(a,a+n);//排序,从小到大的顺序接水  
   for (i=0;i<n;++i)  {    //用贪心法求解   
      j++;
      if (j==r+1) j=1;   //前r个人为一组，第r+1个人回到第一个水龙 
      s[j]+=a[i];     //当前j龙头：接水时间加上等待时间 
      minx+=s[j];
    }
   printf("%d\n",minx);   //输出解答
	return 0;
}