贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
三种策略
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
int w;
int v;
double avg;
}P;
bool cmp(P a,P b){
return a.avg>b.avg;
}
int main(){
P *p;
int n,i,m;//n 物品个数 m背包容量
while(cin>>n>>m){
p=new P[n];
for(i=0;i<n;i++){
cin>>p[i].w>>p[i].v;
p[i].avg=p[i].v/p[i].w*1.0;
}
sort(p,p+n,cmp);
int maxvalue=0;
for(i=0;i<n;i++){
if(p[i].w<=m){
m-=p[i].w;
maxvalue+=p[i].v;
}else{
break;
}
}
cout<<maxvalue<<endl;
}
return 0;
}
(ps:活动结束时间按从小到大排序)
#include<iostream>
#include<algorithm>
using namespace std;
struct actime{
int start,finish;
}act[1002];
bool cmp(actime a,actime b){
return a.finish<b.finish;
}
int main(){
int i,n,t,total;
while(cin>>n){//活动的个数
for(i=0;i<n;i++){
cin>>act[i].start>>act[i].finish;
}
sort(act,act+n,cmp);//按活动结束时间从小到大排序
t=-1;
total=0;
for(i=0;i<n;i++){
if(t<=act[i].start){
total++;
t=act[i].finish;
}
}
cout<<total<<endl;
}
return 0;
}
代码2
#include <iostream>
using namespace std;
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[]);
const int N = 11;
int main()
{
//下标从1开始,存储活动开始时间
int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};
//下标从1开始,存储活动结束时间
int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};
bool A[N+1];
cout<<"各活动的开始时间,结束时间分别为:"<<endl;
for(int i=1;i<=N;i++)
{
cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
}
GreedySelector(N,s,f,A);
cout<<"最大相容活动子集为:"<<endl;
for(int i=1;i<=N;i++)
{
if(A[i]){
cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
}
}
return 0;
}
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
A[1]=true;
int j=1;//记录最近一次加入A中的活动
for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容
{
if (s[i]>=f[j])
{
A[i]=true;
j=i;
}
else
{
A[i]=false;
}
}
}
求一个连通无向图的最小生成树的代价(图边权值为正整数)。
输入
第一行是一个整数N(1<=N<=20),表示有多少个图需要计算。以下有N个图,第i图的第一行是一个整数M(1<=M<=50),表示图的顶点数,第i图的第2行至1+M行为一个M*M的二维矩阵,其元素ai,j表示图的i顶点和j顶点的连接情况,如果ai,j=0,表示i顶点和j顶点不相连;如果ai,j>0,表示i顶点和j顶点的连接权值。
输出
每个用例,用一行输出对应图的最小生成树的代价。
样例输入
1 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0
样例输出
15
模拟过程
#include<iostream>
using namespace std;
struct node
{
int l;
int r;
int len;
node *next;
};
void insert(node *&h,node *p) //指针插入排序
{
node *q=h;
while(q->next && q->next->len <= p->len)
{
q=q->next;
}
p->next=q->next;
q->next=p;
}
int main()
{
// freopen("001.in","r",stdin);
node *h,*p;
int n,m,x,temp;
int *a;
int i,j;
int sum;
cin>>n;
while(n--)
{
sum=0;
cin>>m;
a=new int[m+1];
for (i=1;i<=m;i++)
{
a[i]=i;
}
h=new node;
p=h;
p->next=NULL;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
{
cin>>x;
if (i>j && x!=0)
{
p=new node;
p->l=i;
p->r=j;
p->len=x;
p->next=NULL;
insert(h,p); //调用插入排序
}
}
p=h->next;
while (p)
{
if (a[p->l]!=a[p->r])
{
sum+=p->len;
temp=a[p->l];
for(i=1;i<=m;i++)
if (a[i]==temp)
{
a[i]=a[p->r];
}
}
p=p->next;
}
/* 可以测试程序工作是否正常
p=h->next;
while(p)
{
cout<<p->l<<':';cout<<p->r<<' ';
cout<<p->len<<" ";
p=p->next;
}
*/
cout<<sum<<endl;
}
return 0;
}
image.png
在一个狭窄的走廊里将桌子从一个房间移动到另一个房间,走廊的宽度只能允许一个桌子通过。给出t,表示有t组测试数据。再给出n,表示要移动n个桌子。n下面有n行,每行两个数字,表示将桌子从a房间移到b房间。走廊的分布图如一图所示,每移动一个桌子到达目的地房间需要花10分钟,问移动n个桌子所需要的时间。
3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50
10 20 30
我们首先输入每次移动的出发和结束房间,然后按每次移动的出发房间从小到大排序,然后直至所有的房间移动完毕。(代码1的解释)
#include<iostream>
#include<algorithm>
using namespace std;
struct table{
int from,to;
bool flag;//记录改房间是否被访问过
}moving[205];
bool cmp(table a,table b){
return a.from<b.from;
}
int main(){
int i,T,n;//T代表测试实例个数,n代表每个测试下的table个数
cin>>T;
while(T--){
cin>>n;
for(i=0;i<n;i++){
cin>>moving[i].from>>moving[i].to;
if(moving[i].from > moving[i].to)
{
int temp = moving[i].from;
moving[i].from = moving[i].to;
moving[i].to = temp;
}//可能出发位置比目的地房间大,无论大小,我们都可以看做从小的房间移动到大的房间
if(moving[i].from%2==0){//考虑实际情况,出发房间为偶数是减一,可参照题中给出的图一
moving[i].from--;
}
if(moving[i].to%2==1){//考虑实际情况,结束房间为奇数是加一,
moving[i].to++;
}
moving[i].flag=false;//初始化房间未被访问过
}
sort(moving,moving+n,cmp);//将所有table按出发房间从小到大排序;
bool completion=false;//是否所有的table移动结束
int cnt=-1,priorTo;//priorTo 记录前一个table移动结束的房间
while(!completion){
completion=true;
cnt++;
priorTo=0;
for(i=0;i<n;i++){//每一轮将可以同时移动的table全部移动完:比如2->5,6->10,因为他们没有共用走廊
if(!moving[i].flag&&moving[i].from>priorTo){
moving[i].flag=true;//标记当前table已经移动完毕
priorTo=moving[i].to;
completion=false;
}
}
}
cout<<cnt*10<<endl;
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t,n,count[410],i,start,end,k;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(count,0,sizeof(count));
while(n--)
{
scanf("%d%d",&start,&end);
if(start>end)//可能出发位置比目的地房间大。
{ //无论大小,我们都可以看做从小的房间移动到大的房间
k=start;
start=end;
end=k;
}
if(start%2==0)//考虑实际情况,出发房间为偶数是减一,可参照题中给出的图一
start-=1;
if(end%2==1)//目的地房间为奇数时加一
end+=1;
for(i=start;i<=end;++i)
count[i]+=10;
}
printf("%d\n",*max_element(count,count+400));//STL中寻找数列最大值函数
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAXN 500
using namespace std;
struct temp{
int be,en;
};
bool comp(temp a,temp b){
return a.be<b.be;
}
int main(){
temp my[MAXN];
int m,n,i;
cin>>m;
while(m--){
cin>>n;
i=0;
int a,b,j;
while(i<n){
cin>>a>>b;
if(a>b)a^=b^=a^=b;
my[i].be=(a+1)/2;
my[i++].en=(b+1)/2;
}
sort(my,my+n,comp);
int s=0,out=n,t=0;
int aa[203];
memset(aa,0,sizeof(aa));
for(i=0;i<n;++i){
for(j=my[i].be;j<=my[i].en;++j)aa[j]++;
}
sort(aa,aa+200);
cout<<aa[199]*10<<'\12';
}
return 0;
}
0021算法笔记——【贪心算法】贪心算法与活动安排问题 C++最小生成树问题 C++c语言贪心算法 HDOJ 1050 Moving Tables(经典贪心) 贪心算法——Hdu 1050 Moving Tables HDU Moving Tables (贪心)