educoder贪心算法

贪心算法:

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解  

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 

利用贪心法求解的问题应具备如下2个特征  

1、贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析 

---

1.活动安排

任务描述

学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。

输入格式

第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。 随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)

输出格式

输出安排的最多的活动数

输入样例

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

输出样例

4

贪心策略:以结束时间最早进行排序,计算相容时间活动的最多个数

#include <stdio.h>
#include <algorithm>
#define MAX 100
struct A{
	int B,E;
};
A a[MAX];
bool b[MAX];
int n;
void swap(A &a,A &b)
{
	A t=a;
	a=b;
	b=t;
}
void sort(int l,int r)//快速排序
{
	if(l<r)
	{
		int i=l,j=r;
		A t=a[l];
		while(i<j)
		{
			while(t.E<=a[j].E&&j>l)
				j--;
			while(a[i].E<=t.E&&i<r)
				i++;
			if(i>=j)
				break;
			swap(a[i],a[j]);
		}
		swap(a[j],a[l]);
		sort(l,j-1);
		sort(j+1,r);
	}
	
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&a[i].B,&a[i].E);
	}
	sort(0,n-1);
	
	int j=0;b[0]=true;//第一个活动肯定可以
	int count=1;
	for(int i=1;i<n;i++)
	{
		if(a[i].B>=a[j].E)//活动相容的条件
		{
			j=i;
			b[i]=true;
			count++;
		}
	}

	printf("%d",count);
}

---

2.最优装载问题

任务描述

有一天，海盗截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一但打碎就失去了价值，虽然海盗船足够大，但载重量为C，每件古董的重量为Wi，海盗们如何把尽量多的宝贝装上海盗船呢？

输入格式

第一行输入n，c，代表有n个古董和船的重量 第二行输入n个数，代表每个古董的重量。 1<n,c<100000 每个古董的重量不超过100

输出格式

输出一个数，代表最多装多少个古董

输入样例

8 30 4 10 7 11 3 5 14 2

输出样例

5

贪心策略:宝贝尽量多,那么就尽量先装重量小的

#include <stdio.h>
#define MAX 100
int n,c;
int w[MAX];
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
void sort(int l,int r)//快速排序
{
	if(l<r)
	{
		int i=l,j=r;
		int t=w[l];
//		i++;
		while(i<j)
		{
			while(t<=w[j]&&j>l)
				j--;
			while(w[i]<=t&&i<r)
				i++;
			if(i>=j)
				break;
			swap(w[i],w[j]);
		}
		swap(w[j],w[l]);
		sort(l,j-1);
		sort(j+1,r);
	}
	
}
int main() 
{
	scanf("%d %d",&n,&c); 
	for(int i=0;i<n;i++)
	{
		scanf("%d",&w[i]);
	}
	
	sort(0,n-1);
	int count=0;
	for(int i=0;i<n;i++)
	{
		if(w[i]<=c)
		{
			count++;
			c-=w[i];
		}
	}
	printf("%d",count);
}

---

3.背包问题

任务描述

现在有很多物品（它们是可以分割的）,每个物品有多个，我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入格式

第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数w,v。

输出格式

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

输入样例

3 15 5 10 2 8 3 9

输出样例

65

思路:注意不要想成01背包问题 或者完全背包问题,这个题是单位重量,不仔细看题会做成完全背包问题

#include <stdio.h>
#define MAX 100
int s,m;
int w[MAX],v[MAX];
int dp[MAX][MAX];
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
void sort(int l,int r)
{
	if(l<r)
	{
		int i=l,j=r;
		int t=w[l];
//		i++;
		while(i<j)
		{
			while(t<=w[j]&&j>l)
				j--;
			while(w[i]<=t&&i<r)
				i++;
			if(i>=j)
				break;
			swap(w[i],w[j]);
			swap(v[i],v[j]);
		}
		swap(w[j],w[l]);
		swap(v[i],v[l]);
		sort(l,j-1);
		sort(j+1,r);
	}
	
}
int main() 
{
	scanf("%d %d",&s,&m); 
	for(int i=1;i<=s;i++)
	{
		scanf("%d %d",&w[i],&v[i]);
	}
	
	sort(1,s);
	
	int sum=0;
	for(int i=s;i>=1;i--)
	{
		if(v[i]<=m)
		{
			sum+=w[i]*v[i];
			m-=v[i];
		}
		else if(m>0)
		{
			sum+=m*w[i];
			m-=v[i];
		}
		else
			break;
	}	
	printf("%d",sum);	
}

---

4.会场安排

任务描述

　　假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)

输入格式

第一行有1 个正整数k，表示有k 个待安排的活动。接下来的k 行中，每行有2 个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。

输出格式

将编程计算出的最少会场数

输入样例

5 1 23 12 28 25 35 27 80 36 50

输出样例

3

解法1:

贪心策略:与活动安排一样,唯一不同的是会场多个,调用"活动安排"的策略直到数组全部被标记

解法2:

多个可能的重叠的区间，找出重叠区间的最大个数

解法1代码如下:

#include <stdio.h>
#include <algorithm>
#define MAX 100
struct A{
	int B,E;
};
A a[MAX];
bool b[MAX];//标记数组 活动是否被安排
int n;
void swap(A &a,A &b)
{
	A t=a;
	a=b;
	b=t;
}
void sort(int l,int r)
{
	if(l<r)
	{
		int i=l,j=r;
		A t=a[l];
		while(i<j)
		{
			while(t.E<=a[j].E&&j>l)
				j--;
			while(a[i].E<=t.E&&i<r)
				i++;
			if(i>=j)
				break;
			swap(a[i],a[j]);
		}
		swap(a[j],a[l]);
		sort(l,j-1);
		sort(j+1,r);
	}
	
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&a[i].B,&a[i].E);
	}
	sort(0,n-1);
	
	int count=1;
	for(int k=1;k<n;k++)//遍历每个活动
	{
		if(!b[k])
		{
			int j=0;b[0]=true;
			
			for(int i=1;i<n;i++)
			{
				if(a[i].B>=a[j].E)
				{
					j=i;
					b[i]=true;
				}
			}
			count++;
		}
	}	

	printf("%d",count);
}

解法2代码:(本来说给大家画个图,太丑了,大家还是意会吧)

#include <stdio.h>
#include <algorithm>
#define MAX 100
struct A{
	int val,start;//val为实际值,start为是否是开始下标,是为1,反之为0
};
A a[MAX];
int n;
void swap(A &a,A &val)
{
	A t=a;
	a=val;
	val=t;
}
void sort(int l,int r)
{
	if(l<r)
	{
		int i=l,j=r;
		A t=a[l];
		while(i<j)
		{
			while(t.val<=a[j].val&&j>l)
				j--;
			while(a[i].val<=t.val&&i<r)
				i++;
			if(i>=j)
				break;
			swap(a[i],a[j]);
		}
		swap(a[j],a[l]);
		sort(l,j-1);
		sort(j+1,r);
	}
	
}

int main()
{
	scanf("%d",&n);
	int t=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&a[t++].val,&a[t++].val);
		a[i].start=1;
	}
	sort(0,t-1);
	int max=0,count=0;
	for(int i=0;i<t;i++)
	{
//		printf("%d %d\n",a[i].val,a[i].start);
		if(a[i].start==1)
		{
			count++;
			if(count>max)
				max=count;
		}
		else
			count--;
	}
	printf("%d",max);
}

 

---

5.删数问题

任务描述

有一个长度为n（n <= 240）的正整数，从中取出s（s < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。

输入格式

第一行输入n和s

输出格式

输出一个整数

输入样例

178543 4

输出样例

13

贪心策略:

1.找到数组中递减序列的第一个数删掉(reason:因为如果只能删一个数并不能直接删数字最大的那个,你需要考虑去掉该数后整体最小)

2.如果不存在递减序列(即全是递增序列),删掉最后一个数字即可

3.考虑100100,s=4的情况会得到00,得到的结果不是正整数需要特殊处理(可以记录非0的需要去掉的最小数字)

#include<stdio.h>
#include<string.h>
#define MAX 300
using namespace std;

int t=0;
int b[MAX];
int x=0;

int main()
{
	char n[MAX];//char数组存储长度240的一串数字
	int m;
	scanf("%s",n);
	scanf("%d",&m);
	t=strlen(n);
	int cnti=t;
	for(int i=0;i<t;i++)
	{
		b[i]=int(n[i])-48;//强转出是ASCII值 需要处理
	}

	int cntmax;
	while(m)
	{
		bool flag=false;//标记是否存在递减序列
		for(int i=0;i<t-1;i++)
		{
			if(b[i]>=b[i+1])//存在递减序列
			{
				flag=true;
				if(b[i+1]==0&&b[i]!=0)
				{
					
					cntmax=b[i];
				}
				for(int j=i;j<t-1;j++)//顺次左移覆盖
				{
					b[j]=b[j+1];
				}
				m--;
				t--;
				break;
			}
		}
		if(!flag)//不存在递减序列 长度t-- 相当于删掉最后一个数字
			{
				m--;
				t--;
			}
		
	}
	int count=0;
	for(int i=0;i<t;i++)
	{
		if(b[i]==0)//处理后的数组中0的个数
			count++;
	}

	if(count==t)//若0的个数与数组长度相同 即结果不是正整数 不合法
	{
		b[t-1]=cntmax;
	}
		
	for(int i=0;i<t;i++)
	{
		printf("%d",b[i]);
	}
	return 0;
} 

---

贪心算法拓展

任务描述

本关任务：掌握贪心算法的算法思想，并能利用贪心算法的算法思想解决删除数字问题。

给定n个纯数字组成的数字串，删除其中k(k<n)个数字后，剩下的数字按原来的秩序组成一个新的正整数，确定删除方案，使得剩下的数字组成的新的正整数最大。

测试输入：

79502867154829179316 8

预期输出：

987829179316

贪心策略：与删数问题相同，唯一不同的是此次求最大且大数可用字符串进行存储，并将比较大小的符号换一下即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    
    char s[1001];
    int a[1001];
    int k;
    int n,i,j;

	cin>>s;
	cin>>k;
	n=strlen(s);
	for(int i=0;i<n;i++)
		a[i]=s[i]-48;

	cout<<endl;
	while(k)
	{
		bool flag=false;
		for(i=0;i<n-1;i++)
		{
			if(a[i]<a[i+1])
			{
				for(j=i;j<n-1;j++)
				{
					a[j]=a[j+1];
				}
				k--;
				n--;
				flag=true;
				break;
			}
		}
		if(!flag)
		{
			n--;
			k--;
		}
	}
	
	for(int i=0;i<n;i++)
	{
		cout<<a[i];
	}
    
    return 0;
}