精华内容
下载资源
问答
  • 贪心

    千次阅读 2018-04-03 21:10:38
    贪心的定义: 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的...

    贪心的定义:

           贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择的性质,我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

    最优子结构:

    当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响,而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前的选择结果对当前进行选择,有回退功能。动态规划主要运用于二维或三维问题,而贪心一般是一维问题 。

    例题:

    确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。 
    作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目) 
     

    Input

    输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。 
     

    Output

    对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。
     

    Sample Input

    
        
    12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0
     

    Sample Output

    
        
    5

    解析:

        要看尽可能多的电视节目,首先需要尽可能的每时每刻都在看,而且还要考虑不能看那种时间特别长的节目,这会让我们因为一个节目而浪费许多时间,首先可以把节目的开始和结束时间存到一个结构体数组中,然后对结构体数组根据结束时间进行排序,然后从第一个节目开始看,如果下一个节目的开始时间早于上一个的结束时间,这个节目就不能看了,然后继续看下一个节目,如果下一个节目的开始时间晚于上一个的话,就可以看这一个节目,然后结束时间需要更新成这一个节目的结束时间。

    #include<iostream>
    #include <deque>
    #include<stack>
    #include<queue>
    #include<math.h>
    #include<algorithm>
    #include<stdlib.h>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    typedef long long LL;
    #define $ 3.141592654
    using namespace std;
    struct W
    {
        int a,b;
    
    };
    bool cmp(struct W x,struct W y)
    {
        return x.b<y.b;
    }
    int main()
    {
        for(;;)
        {
            int n,i,j=1,k;
            struct W w[100];
            scanf("%d",&n);
            if(n==0)
                break;
            for(i=0;i<n;i++)
                scanf("%d%d",&w[i].a,&w[i].b);
            sort(w,w+n,cmp);
            k=w[0].b;
            for(i=1;i<n;i++)
            {
                if(w[i].a<k)
                    continue;
                else
                {
                    j++;
                    k=w[i].b;
                }
            }
            printf("%d\n",j);
    
        }
        return 0;
    }
    
    
    贪心最重要的一点就是“贪”,贪就是尽可能的获取一个最优的解,做题时首先要思考如何实现最优解。
    展开全文
  • 贪心_贪心_源码

    2021-10-04 12:16:59
    贪心相关程序,用于求解各类常见的贪心问题,能够有一个很好的收获
  • 贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
  • 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
  • 从零开始学贪心算法

    万次阅读 多人点赞 2016-05-08 00:00:01
    贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 解题的一般步骤是: 1.建立数学模
    本文在写作过程中参考了大量资料,不能一一列举,还请见谅。
    
    贪心算法的定义:
    贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
    解题的一般步骤是:
    1.建立数学模型来描述问题;
    2.把求解的问题分成若干个子问题;
    3.对每一子问题求解,得到子问题的局部最优解;
    4.把子问题的局部最优解合成原来问题的一个解。
    如果大家比较了解动态规划,就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法,我们自底向上构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。
    话不多说,我们来看几个具体的例子慢慢理解它:
    1.活动选择问题
     这是《算法导论》上的例子,也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后,活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠,ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S,其中各项活动按照结束时间单调递增排序。


    考虑使用贪心算法的解法。为了方便,我们用不同颜色的线条代表每个活动,线条的长度就是活动所占据的时间段,蓝色的线条表示我们已经选择的活动;红色的线条表示我们没有选择的活动。
    如果我们每次都选择开始时间最早的活动,不能得到最优解:


    如果我们每次都选择持续时间最短的活动,不能得到最优解:


    可以用数学归纳法证明,我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解,按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。

    #include<cstdio>
    #include<iostream> 
    #include<algorithm> 
    using namespace std;    
    int N;
    struct Act
    {
    	int start;
    	int end;
    }act[100010];
    
    bool cmp(Act a,Act b)  
    {  
        return a.end<b.end;  
    } 
    
    int greedy_activity_selector()  
    {  
    	int num=1,i=1;   
        for(int j=2;j<=N;j++)  
        {  
            if(act[j].start>=act[i].end)  
            {  
                i=j;  
                num++;  
            }  
        }  
        return num;
    }
    
    int main()  
    {  
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&N);
    		for(int i=1;i<=N;i++)
    		{
    			scanf("%lld %lld",&act[i].start,&act[i].end);
    		}
    		act[0].start=-1;
    		act[0].end=-1;
    	 	sort(act+1,act+N+1,cmp); 
        	int res=greedy_activity_selector();
    		cout<<res<<endl;  
    	}
    }  
    
    2.钱币找零问题
    这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?用贪心算法的思想,很显然,每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=7; 
    int Count[N]={3,0,2,1,0,3,5};
    int Value[N]={1,2,5,10,20,50,100};
      
    int solve(int money) 
    {
    	int num=0;
    	for(int i=N-1;i>=0;i--) 
    	{
    		int c=min(money/Value[i],Count[i]);
    		money=money-c*Value[i];
    		num+=c;
    	}
    	if(money>0) num=-1;
    	return num;
    }
     
    int main() 
    {
    	int money;
    	cin>>money;
    	int res=solve(money);
    	if(res!=-1) cout<<res<<endl;
    	else cout<<"NO"<<endl;
    }
    3.再论背包问题
    从零开始学动态规划中我们已经谈过三种最基本的背包问题:零一背包,部分背包,完全背包。很容易证明,背包问题不能使用贪心算法。然而我们考虑这样一种背包问题:在选择物品i装入背包时,可以选择物品的一部分,而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标,选择单位重量价值最高的物品,将尽可能多的该物品装入背包,依此策略一直地进行下去,直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。
    #include<iostream>   
    using namespace std;   
    const int N=4;  
    void knapsack(float M,float v[],float w[],float x[]);  
      
    int main()  
    {  
        float M=50;
    	//背包所能容纳的重量   
        float w[]={0,10,30,20,5};
    	//每种物品的重量  
        float v[]={0,200,400,100,10};  
      	//每种物品的价值 
        float x[N+1]={0};  
        //记录结果的数组 
        knapsack(M,v,w,x);  
        cout<<"选择装下的物品比例:"<<endl;  
        for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;  
    }  
      
    void knapsack(float M,float v[],float w[],float x[])  
    {  
        int i;  
        //物品整件被装下  
        for(i=1;i<=N;i++)
        {  
            if(w[i]>M) break;   
            x[i]=1;  
            M-=w[i];  
        }   
        //物品部分被装下  
        if(i<=N) x[i]=M/w[i];   
    } 

    4.多机调度问题
    n个作业组成的作业集,可由m台相同机器加工处理。要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业;每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题,还没有有效的解法(求最优解),但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时,只要将作业时间区间分配给作业即可;当n>m时,首先将n个作业从大到小排序,然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中,选择需要处理时间最长的,然后依次选择处理时间次长的,直到所有的作业全部处理完毕,或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器,那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况,这样势必效率较低。在下面的代码中没有讨论n和m的大小关系,把这两种情况合二为一了。

    #include<iostream>  
    #include<algorithm>    
    using namespace std;  
    int speed[10010];  
    int mintime[110];  
    
    bool cmp( const int &x,const int &y)  
    {  
        return x>y;  
    }  
    
    int main()  
    {  
    	int n,m;         
    	memset(speed,0,sizeof(speed));  
     	memset(mintime,0,sizeof(mintime));  
      	cin>>n>>m;  
       	for(int i=0;i<n;++i) cin>>speed[i];  
        sort(speed,speed+n,cmp);  
        for(int i=0;i<n;++i)   
        { 
        	*min_element(mintime,mintime+m)+=speed[i];   
       	}   
        cout<<*max_element(mintime,mintime+m)<<endl; 
    }

    5.小船过河问题
    POJ1700是一道经典的贪心算法例题。题目大意是只有一艘船,能乘2人,船的运行速度为2人中较慢一人的速度,过去后还需一个人把船划回来,问把n个人运到对岸,最少需要多久。先将所有人过河所需的时间按照升序排序,我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去,有两种方式:
    1.最快的和次快的过河,然后最快的将船划回来;次慢的和最慢的过河,然后次快的将船划回来,所需时间为:t[0]+2*t[1]+t[n-1];
    2.最快的和最慢的过河,然后最快的将船划回来,最快的和次慢的过河,然后最快的将船划回来,所需时间为:2*t[0]+t[n-2]+t[n-1]。
    算一下就知道,除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人,问题具有贪心子结构的性质。
    AC代码:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
    	int a[1000],t,n,sum;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		sum=0;
            for(int i=0;i<n;i++) scanf("%d",&a[i]);
            while(n>3)
    		{
    			sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);
                n-=2;
            }
            if(n==3) sum+=a[0]+a[1]+a[2];
            else if(n==2) sum+=a[1];
            else sum+=a[0];
            printf("%d\n",sum);
    	}
    }

    6.区间覆盖问题
    POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧,而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上,只能覆盖d距离,所以如果小岛能够被覆盖到的话,它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛,我们可以计算出一个雷达所在位置的区间。


    问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序,初始时需要一个点。如果两个区间相交而不重合,我们什么都不需要做;如果一个区间完全包含于另外一个区间,我们需要更新区间的右端点;如果两个区间不相交,我们需要增加点并更新右端点。
    AC代码:

    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct Point
    {
    	double x;
    	double y;
    }point[1000];
    
    int cmp(const void *a, const void *b)
    {
        return (*(Point *)a).x>(*(Point *)b).x?1:-1;
    }
    
    int main()
    {
    	int n,d;
    	int num=1;
    	while(cin>>n>>d)
    	{
    		int counting=1;
    		if(n==0&&d==0) break;
    		for(int i=0;i<n;i++)
    		{
    			int x,y;
    			cin>>x>>y;
    			if(y>d)
    			{
    				counting=-1;
    			}
    			double t=sqrt(d*d-y*y);
    			//转化为最少区间的问题 
    			point[i].x=x-t;
    			//区间左端点 
    			point[i].y=x+t;
    			//区间右端点 
    		}
    		if(counting!=-1)
    		{
    			qsort(point,n,sizeof(point[0]),cmp);
    			//按区间左端点排序 
    			double s=point[0].y;
    			//区间右端点 
    			for(int i=1;i<n;i++)
    			{
    				if(point[i].x>s)
    				//如果两个区间没有重合,增加雷达数目并更新右端点 
    				{
    					counting++;
    					s=point[i].y; 
    				}
    				else if(point[i].y<s)
    				//如果第二个区间被完全包含于第一个区间,更新右端点 
    				{
    					s=point[i].y;
    				}
    			}
    		}
    		cout<<"Case "<<num<<':'<<' '<<counting<<endl;
    		num++; 
    	}
    }	

    7.销售比赛
    在学校OJ上做的一道比较好的题,这里码一下。假设有偶数天,要求每天必须买一件物品或者卖一件物品,只能选择一种操作并且不能不选,开始手上没有这种物品。现在给你每天的物品价格表,要求计算最大收益。首先要明白,第一天必须买,最后一天必须卖,并且最后手上没有物品。那么除了第一天和最后一天之外我们每次取两天,小的买大的卖,并且把卖的价格放进一个最小堆。如果买的价格比堆顶还大,就交换。这样我们保证了卖的价格总是大于买的价格,一定能取得最大收益。

    #include<queue>
    #include<vector>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    long long int price[100010],t,n,res;
           
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>t;
        while(t--)
        {
            cin>>n;
            priority_queue<long long int, vector<long long int>, greater<long long int> > q;
            res=0;
            for(int i=1;i<=n;i++)
            {
                cin>>price[i];
            }
            res-=price[1];
            res+=price[n];
            for(int i=2;i<=n-1;i=i+2)
            {
                long long int buy=min(price[i],price[i+1]);
                long long int sell=max(price[i],price[i+1]);
                if(!q.empty())
                {
                    if(buy>q.top())
                    {
                        res=res-2*q.top()+buy+sell;
                        q.pop();
                        q.push(buy);
                        q.push(sell);
                    }
                    else
                    {
                        res=res-buy+sell;
                        q.push(sell);
                    }
                }
                else
                {
                    res=res-buy+sell;
                    q.push(sell);
                }
            }     
            cout<<res<<endl;
        }
    }

    下面我们结合数据结构中的知识讲解几个例子。
    8.Huffman编码
    这同样是《算法导论》上的例子。Huffman编码是广泛用于数据文件压缩的十分有效的编码方法。我们可以有多种方式表示文件中的信息,如果用01串表示字符,采用定长编码表示,则需要3位表示一个字符,整个文件编码需要300000位;采用变长编码表示,给频率高的字符较短的编码,频率低的字符较长的编码,达到整体编码减少的目的,则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位,由此可见,变长码比定长码方案好,总码长减小约25%。


     对每一个字符规定一个01串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀,这种编码称为前缀码。可能无前缀码是一个更好的名字,但是前缀码是一致认可的标准术语。编码的前缀性质可以使译码非常简单:例如001011101可以唯一的分解为0,0,101,1101,因而其译码为aabe。译码过程需要方便的取出编码的前缀,为此可以用二叉树作为前缀码的数据结构:树叶表示给定字符;从树根到树叶的路径当作该字符的前缀码;代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标。


    从上图可以看出,最优前缀编码码的二叉树总是一棵完全二叉树,而定长编码的二叉树不是一棵完全二叉树。 给定编码字符集C及频率分布f,C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c),dT(c)也是字符c的前缀码长。则平均码长定义为:


    使平均码长达到最小的前缀码编码方案称为C的最优前缀码。     
    Huffman编码的构造方法:先合并最小频率的2个字符对应的子树,计算合并后的子树的频率;重新排序各个子树;对上述排序后的子树序列进行合并;重复上述过程,将全部结点合并成1棵完整的二叉树;对二叉树中的边赋予0、1,得到各字符的变长编码。


    POJ3253一道就是利用这一思想的典型例题。题目大意是有把一块无限长的木板锯成几块给定长度的小木板,每次锯都需要一定费用,费用就是当前锯的木板的长度。给定各个要求的小木板的长度以及小木板的个数,求最小的费用。以要求3块长度分别为5,8,5的木板为例:先从无限长的木板上锯下长度为21的木板,花费21;再从长度为21的木板上锯下长度为5的木板,花费5;再从长度为16的木板上锯下长度为8的木板,花费8;总花费=21+5+8=34。利用Huffman思想,要使总费用最小,那么每次只选取最小长度的两块木板相加,再把这些和累加到总费用中即可。为了提高效率,使用优先队列优化,并且还要注意使用long long int保存结果。
    AC代码:

    #include<queue>
    #include<cstdio>
    #include<iostream>
    using namespace std;
    
    int main()
    {
        long long int sum;
        int i,n,t,a,b;
        while(~scanf("%d",&n))
        {
            priority_queue<int,vector<int>,greater<int> >q;
            for(i=0;i<n;i++)
            {
    			scanf("%d",&t);
    			q.push(t);
            }
            sum=0;
            if(q.size()==1)
            {
                a=q.top();
                sum+=a;
                q.pop();
            }
            while(q.size()>1)
            {
                a=q.top();
                q.pop();
                b=q.top();
                q.pop();
                t=a+b;
                sum+=t;
                q.push(t);
            }
            printf("%lld\n",sum);
        }
    }

    9.Dijkstra算法
    Dijkstra算法是由E.W.Dijkstra于1959年提出,是目前公认的最好的求解最短路径的方法,使用的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的最短路径问题,其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点,简单的说就是bfs+贪心算法的思想。

    #include<iostream>
    #include<algorithm> 
    #define INF 1000 
    #define MAX_V 100
    using namespace std;  
    
    int main()
    {
    	int V,E;
    	int i,j,m,n;
    	int cost[MAX_V][MAX_V];
    	int d[MAX_V];
    	bool used[MAX_V];
    	cin>>V>>E;
    	fill(d,d+V+1,INF);
    	fill(used,used+V,false);
    	for(i=0;i<V;i++)
    	{
    		for(j=0;j<V;j++)
    		{
    			if(i==j) cost[i][j]=0;
    			else cost[i][j]=INF;
    		}
    	}
    	for(m=0;m<E;m++)
    	{
    		cin>>i>>j>>cost[i][j];
    		cost[j][i]=cost[i][j];
    	}
    	cin>>n;
    	d[n]=0;
    	//源点 
    	while(true)
    	{
    		int v=V;
    		for(m=0;m<V;m++)
    		{	
    			if((!used[m])&&(d[m]<d[v])) v=m;
    		}	
    		if(v==V) break;
    		used[v]=true;
    		for(m=0;m<V;m++)
    		{
    			d[m]=min(d[m],d[v]+cost[v][m]); 
    		}
    	}
    	for(i=0;i<V;i++)
    	{
    		cout<<"the shortest distance between "<<n<<" and "<<i<<" is "<<d[i]<<endl;
    	}
    }
    
    10.最小生成树算法
    设一个网络表示为无向连通带权图G =(V, E) , E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树的代价是指生成树上各边权的总和,在G的所有生成树中,耗费最小的生成树称为G的最小生成树。例如在设计通信网络时,用图的顶点表示城市,用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用,最小生成树给出建立通信网络的最经济方案。


    构造最小生成树的Kruskal算法和Prim算法都利用了MST(最小生成树)性质:设顶点集U是V的真子集(可以任意选取),如果(u,v)∈E为横跨点集U和V—U的边,即u∈U,v∈V- U,并且在所有这样的边中,(u,v)的权c[u][v]最小,则一定存在G的一棵最小生成树,它以(u,v)为其中一条边。



    使用反证法可以很简单的证明此性质。假设对G的任意一个最小生成树T,针对点集U和V—U,(u,v)∈E为横跨这2个点集的最小权边,T不包含该最小权边<u, v>,但T包括节点u和v。将<u,v>添加到树T中,树T将变为含回路的子图,并且该回路上有一条不同于<u,v>的边<u’,v’>,u’∈U,v’∈V-U。将<u’,v’>删去,得到另一个树T’,即树T’是通过将T中的边<u’,v’>替换为<u,v>得到的。由于这2条边的耗费满足c[u][v]≤c[u’][v’],故即T’耗费≤T的耗费,这与T是任意最小生成树的假设相矛盾,从而得证。


    Prim算法每一步都选择连接U和V-U的权值最小的边加入生成树。


    #include<iostream>
    #include<algorithm>
    #define MAX_V 100
    #define INF 1000 
    using namespace std;  
    
    int main()
    {
    	int V,E;
    	int i,j,m,n;
    	int cost[MAX_V][MAX_V];
    	int mincost[MAX_V];
    	bool used[MAX_V];
    	cin>>V>>E;
    	fill(mincost,mincost+V+1,INF);
    	fill(used,used+V,false);
    	for(i=0;i<V;i++)
    	{
    		for(j=0;j<V;j++)
    		{
    			if(i==j) cost[i][j]=0;
    			else cost[i][j]=INF; 
    		}
    	}
    	for(m=0;m<E;m++)
    	{
    		cin>>i>>j>>cost[i][j];
    		cost[j][i]=cost[i][j];
    	}
    	mincost[0]=0;
    	int res=0;
    	while(true)
    	{
    		int v=V;
    		for(m=0;m<V;m++)
    		{	
    			if((!used[m])&&(mincost[m]<mincost[v]))
    				v=m;
    		}	
    		if(v==V) break;
    		used[v]=true;
    		res+=mincost[v];
    		for(m=0;m<V;m++)
    		{
    			mincost[m]=min(mincost[m],cost[v][m]); 
    		}
    	}
    	cout<<res<<endl;
    }
    
    Kruskal算法每一步直接将权值最小的不成环的边加入生成树,我们借助并查集这一数据结构可以完美实现它。


    #include<iostream>
    #include<algorithm> 
    #define MAX_E 100 
    using namespace std;  
    struct edge
    {
    	int u,v,cost;	
    };
    int pre[MAX_E];
    edge es[MAX_E];
    int find(int x);
    void initvalue(int x);
    bool same(int x,int y);
    void unite(int x,int y);
    bool comp(const edge& e1,const edge& e2);
    
    int main()
    {
    	int V,E;
    	int i,j,m,n; 
    	cin>>V>>E;
    	initvalue(V);
    	for(i=0;i<E;i++) cin>>es[i].u>>es[i].v>>es[i].cost;		
    	sort(es,es+E,comp);
    	int res=0;
    	for(i=0;i<E;i++)
    	{
    		edge e=es[i];
    		if(!same(e.u,e.v))
    		{
    			unite(e.u,e.v);
    			res+=e.cost;
    		}
    	}
    	cout<<res<<endl;	
    }
    
    bool comp(const edge& e1,const edge& e2)
    {
    	return e1.cost<e2.cost;	
    }
    
    void initvalue(int x)
    {
    	for(int i=0;i<x;i++) pre[i]=i;
    }
    
    int find(int x)
    {
    	int r=x;
    	while(pre[r]!=r) r=pre[r];
    	int i=x,j;
    	while(pre[i]!=r)
    	{
    		j=pre[i];
    		pre[i]=r;
    		i=j;
    	}
    	return r;
    }
    
    bool same(int x,int y)
    {
    	if(find(x)==find(y)) return true;
    	else return false;	
    }
    
    void unite(int x,int y)
    {
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy) pre[fx]=fy;	
    }
    
    关于贪心算法的基础知识就简要介绍到这里,希望能作为大家继续深入学习的基础。

    展开全文
  • 贪心_贪心算法_源码

    2021-10-03 06:31:34
    大一新手之贪心算法观赏练习,适合初学者使用!内含PPT和例题,请配合食用
  • 贪心算法 贪心算法的理解 贪心算法的算法 贪心算法的讲解
  • 贪心算法

    千次阅读 2019-10-24 17:27:47
    贪心算法

    455. 分发饼干

    https://leetcode-cn.com/problems/assign-cookies/

     

     把最大的饼干最贪心的小朋友,如果无法满足就往前面找次贪心的小朋友

     

    /// 455. Assign Cookies
    /// https://leetcode.com/problems/assign-cookies/description/
    /// 先尝试满足最贪心的小朋友
    /// 时间复杂度: O(nlogn)
    /// 空间复杂度: O(1)
    public class Solution {
        public int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int gi = g.length - 1, si = s.length - 1;
            int res = 0;
            while (gi >= 0 && si >= 0) {
                if (s[si] >= g[gi]) {
                    res++;
                    si--;
                }
                gi--;
            }
            return res;
        }
        //public static void main(String[] args) {
        //    int g1[] = {1, 2, 3};
        //    int s1[] = {1, 1};
        //    System.out.println((new Solution()).findContentChildren(g1, s1));
        //    int g2[] = {1, 2};
        //    int s2[] = {1, 2, 3};
        //    System.out.println((new Solution()).findContentChildren(g2, s2));
        //}
    }
    //C++
    /// 455. Assign Cookies
    /// https://leetcode.com/problems/assign-cookies/description/
    /// 先尝试满足最贪心的小朋友
    /// 时间复杂度: O(nlogn)
    /// 空间复杂度: O(1)
    class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
            sort(g.begin(), g.end(), greater<int>());
            sort(s.begin(), s.end(), greater<int>());
            int gi = 0, si = 0;
            int res = 0;
            while(gi < g.size() && si < s.size()){
                if(s[si] >= g[gi]){
                    res ++;
                    si ++;
                    gi ++;
                }else{
                    gi ++;
                }
            }
            return res;
        }
    };
    //int main() {
    //    int g1[] = {1, 2, 3};
    //    vector<int> gv1(g1, g1 + sizeof(g1)/sizeof(int));
    //    int s1[] = {1, 1};
    //    vector<int> sv1(s1, s1 + sizeof(s1)/sizeof(int));
    //    cout << Solution().findContentChildren(gv1, sv1) << endl;
    //    int g2[] = {1, 2};
    //    vector<int> gv2(g2, g2 + sizeof(g2)/sizeof(int));
    //    int s2[] = {1, 2, 3};
    //    vector<int> sv2(s2, s2 + sizeof(s2)/sizeof(int));
    //    cout << Solution().findContentChildren(gv2, sv2) << endl;
    //    return 0;
    //}

     

    /// 455. Assign Cookies
    /// https://leetcode.com/problems/assign-cookies/description/
    /// 先尝试满足最不贪心的小朋友
    /// 时间复杂度: O(nlogn)
    /// 空间复杂度: O(1)
    public class Solution2 {
        public int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int gi = 0, si = 0;
            int res = 0;
            while (gi < g.length && si < s.length) {
                if (s[si] >= g[gi]) {
                    res++;
                    gi++;
                }
                si++;
            }
            return res;
        }
        //public static void main(String[] args) {
        //    int g1[] = {1, 2, 3};
        //    int s1[] = {1, 1};
        //    System.out.println((new Solution2()).findContentChildren(g1, s1));
        //    int g2[] = {1, 2};
        //    int s2[] = {1, 2, 3};
        //    System.out.println((new Solution2()).findContentChildren(g2, s2));
        //}
    }

    392. 判断子序列 

    https://leetcode-cn.com/problems/is-subsequence/

     

    展开全文
  • 贪心算法的定义 贪心算法的基本思想 贪心算法的实现思路 贪心算法的基本要素 贪心算法的特点 贪心算法存在的问题 ;贪心算法 又称贪婪算法可以简单描述为对一组数据进行排序找出最小值进行处理再找出最小值再处理也...
  • 贪心

    2020-03-22 08:19:41
    贪心法什么是贪心贪心法求解的问题应具有的性质贪心选择性质最优子结构性质贪心法的一般求解过程 什么是贪心贪心法的基本思路是在对问题求解时总是做出在当前看来是最好的选择,也就是说贪心法不从整体最优上...

    什么是贪心法

    贪心法的基本思路是在对问题求解时总是做出在当前看来是最好的选择,也就是说贪心法不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。
    人们通常希望找到整体最优解,所以采用贪心法需要证明设计的算法确实是整体最优解或求解了它要解决的问题。
    贪心法从问题的某一个初始解{}出发,采用逐步构造最优解的方法向给定的目标前进,每一步决策产生n-元组解(x0,x1,…,xn-1)的一个分量。
    贪心法每一步上用作决策依据的选择准则被称为最优量度标准(或贪心准则),也就是说,在选择解分量的过程中,添加新的解分量xk后,形成的部分解(x0,x1,…,xk)不违反可行解约束条件。
    每一次贪心选择都将所求问题简化为规模更小的子问题,并期望通过每次所做的局部最优选择产生出一个全局最优解。

    贪心法求解的问题应具有的性质

    贪心选择性质

    所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
    也就是说,贪心法仅在当前状态下做出最好选择,即局部最优选择,然后再去求解做出这个选择后产生的相应子问题的解。

    最优子结构性质

    如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。
    问题的最优子结构性质是该问题可用动态规划算法或贪心法求解的关键特征。

    贪心法的一般求解过程

    SolutionType Greedy(SType a[],int n)
    //假设解向量(x0,x1,…,xn-1)类型为SolutionType,其分量为SType类型
    {  SolutionType x={}//初始时,解向量不包含任何分量
       for (int i=0;i<n;i++)	  //执行n步操作
       {  SType xi=Select(a);	  //从输入a中选择一个当前最好的分量
          if (Feasiable(xi))	  //判断xi是否包含在当前解中
    	 solution=Union(x,xi);	  //将xi分量合并形成x 
       }
       return x;			  //返回生成的最优解
    }
    
    展开全文
  • 贪心算法汽车加油问题 贪心算法基本思想 贪心算法总是做出在当前看来是最好的选择并不会从总体去最优考虑虽然贪心算法不会对所有问题找到最优但是有时候会得到最优解的近似解 贪心算法的基本要素 1贪心选择性质指所...
  • 贪心算法课件

    2018-01-05 17:16:14
    贪心算法课件 算法导论 讲述了与动态规划的区别 贪心算法的要诀
  • 完成算法实践作业,实现贪心算法中的硬币问题
  • 贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
  • 贪心算法-源码

    2021-02-10 12:40:23
    贪心算法
  • 福建工程学院计算机与信息科学系 实验报告 1 2 3 4 5 篇二北邮算法作业贪心算法实验报告 第三次算法作业贪心算法 姓名吴迪 班级08211312 学号08211488 班内序号 15 摘要本文为完成作业problem1problem3problem4...
  • 贪心贪心法 补充内容 算法
  • 主要针对贪心算法原理及实现和在动态规划中的应用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 215,160
精华内容 86,064
关键字:

贪心