贪心算法学习记录

目录

• • • 一、活动安排问题
    • 二、最优装载问题
    • 三、背包问题(贪心版本 可拆分版本)
    • 五、删数问题

qsort()中cmp函数用法：
https://blog.csdn.net/m0_51627418/article/details/121246105?spm=1001.2014.3001.5502

一、活动安排问题

输入样例

11
1 4
3 6
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14  

输出样例

4  

分析：
对每一个活动按照占用会场时间排序，其实也是按照结束时间来排序的。因为安排一个活动后，在这个活动结束时间之前，是不能在安排活动的。就可以分为结束时间相等和不等两种情况来判断。这里的cmp：如果结束时间一样，就找是开始时间小的（这样占用时间最短）；如果结束时间不一样就是就找最早结束的。
这里的代码实现原理：

cmp()会有三种返回值（以qsort为例）:
1、返回一个正数：a排列在b之后；
2、返回0：a、b相等；
3、返回一个负数：a排在b之前；

过题C语言代码：

// #include
// using namespace std;
#include
#include
int cmp(const void* a,const void* b){
    if(((int *)a)[1]==((int *)b)[1]) return  ((int *)a)[0]-((int *)b)[0];
    else return ((int *)a)[1]-((int *)b)[1];
}
int main(){
    int n;
    scanf("%d",&n);
    int a[n+5][2];
    for(int i = 0; i <n;i++)   scanf("%d%d",&a[i][0],&a[i][1]);
    qsort(a,n,2*sizeof(int),cmp);
    int count = 1, j = 0;
    for(int i = 1; i <n;i++){
            if(a[i][0]>=a[j][1]){
                j = i;
                count ++;
            }        
    }
    printf("%d",count);
    return 0;
} 

二、最优装载问题

输入样例

8 30
4 10 7 11 3 5 14 2  

输出样例

5

就是一个选最小没啥可说的
解题代码：

//#include
//using namespace std;
#include
#include
int cmp(const void* a,const void* b){
	return *((int*)a) - *((int*)b);
}
int main(){
	int n,m,cnt = 0;
	scanf("%d%d",&n,&m);
	int a[n+10];
	for(int i = 0; i < n;i++){
		scanf("%d",&a[i]);
	}
	qsort(a,n,sizeof(int),cmp);
	int sum= 0;
	for(int i = 0; i < n; i++){
		sum += a[i];
		if(sum>m) break; 
		cnt++;
	}
	printf("%d",cnt);
	return 0;
}
 

三、背包问题(贪心版本 可拆分版本)

输入样例

3 15
5 10
2 8
3 9  

输出样例

60  

分析：
其实这因该是一个思维题吧。可以拆分，就直接每个物品都拆为单位重量价值。然后查找最大的单位重量价值，乘以背包容量，就是背包所能装的最大价值。

过题代码：

#include
#include
#include
//#include
//using namespace std;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
  	double x,y;
  	double a[n+10];
    for(int i = 0; i <n;i++){
    	scanf("%d%d",&x,&y);
    	a[i] = y/x;
	} 
	int t = 0;
    for(int j = 1,i=0;j<n;j++){
    	if(a[j]>a[i])  t = a[i],a[i]= a[j],a[j]= t;
	}
	int ans = m*a[0];
   	printf("%d",ans);
    return 0;
}

五、删数问题

输入样例

178543 4  

输出样例

13  

思路：

过题代码：

#include
#include
#include
//#include
//using namespace std;
int main(){
	char ch[240];	
	int a[250],cnt = 0;
	scanf("%s",ch); 
    for(int i = 0; ch[i]!=';'++i)++{
    	cnt ;[
		a]i= [ ch]i- '0';}
	int
	
	= ccnt 0,=s 0 ;printf 
	("%d",[a0]);for
	
	(int= i 1 ;< i ;cnt++i)if{
		(<ccnt4&&[a]s<[a]i)++ ccnt;else
		printf{
			("%d",[a]i);=
			s ; i}
		} 
	return
	0 ;}