C++数据结构与算法（贪婪算法）

谁借莪１个温暖的怀抱￠ 2021-11-10 10:44 373阅读 0赞

>  **贪婪算法（Greedy Method）**也称贪心算法，在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦做出，就不可再更改。也就是说，它总是做出局部最优解的最优化问题。做出贪婪决策的依据称为贪婪准则（Greedy Criterion）.
> 
> 贪心算法并不保证得到最优解，对许多问题确实可以求得最优解。

# 1 案例分析 #

## 1） 装箱问题 ##

> 确定箱子的体积大小为10，输入物品的个数及其每个物品的体积，输出至少需要几个箱子并且输出每个箱子装哪几个物品。
> 
> 输入（每个物品的体积）：
> 
> 8
> 
> 2
> 
> 3
> 
> 4
> 
> 5
> 
> 6
> 
> 3
> 
> 2
> 
> 1
> 
> 输出（每个箱子装的物品）：
> 
> 5 3
> 
> 4 2 1
> 
> 6 7 8
> 
> **解题思路：将输入的每个物品的大小进行排序，然后初始化一个箱子，如果为空就装入，然后计算剩余体积，然后看下一个物品的体积能否装下，如能装下就装箱，若不能装下就再初始化一个箱子，直至将所有的物品装完。原则：浪费空间最小。**

#include<stdio.h>
    #include<stdlib.h>
    #define V 10         //V代表箱子的容积
    
    //存放物品信息的类型
    typedef struct{
    	int gno; //物品编号
    	int gv;  //物品体积
    }ElemG;
    
    //物品结点
    typedef struct node{
    	int gno;   //物品编号
    	struct node *link;   //物品结点间的指针
    }Goodslink;
    
    //创建箱子结点
    typedef struct box{
    	int remainder;   //箱子剩余体积
    	Goodslink *hg;  //物品结点头指针
    	struct box *next;  //箱子结点间的指针
    }Boxlink;
    
    //排序
    void SortD(ElemG *g,int n)
    {
    	ElemG t;
    	int i,j;
    	for(i=0;i<n-1;i++)
    	{
    		for(j=i+1;j<n;j++)
    			if(g[i].gv<g[j].gv)
    			{
    				t=g[i];
    				g[i]=g[j];
    				g[j]=t;
    			}
    	}
    }
    
    //装箱
    Boxlink * Packing(ElemG *g,int n)
    {
    	Boxlink *hbox=NULL,*tail,*p;
    	int i;
    	Goodslink *q,*newg;
    	for(i=0;i<n;i++)
    	{
    		for(p=hbox;p&&p->remainder<g[i].gv;p=p->next);
    		if(!p)                  //若该箱子不是头结点或者箱子装不下
    		{
    			p=(Boxlink *)malloc(sizeof(Boxlink));
    			p->remainder=V;                 //开始初始化一个箱子
    			p->hg=p->next=NULL;
    			if(!hbox)                       //箱子为空
    				hbox=tail=p;
    			else                            //箱子不为空
    				tail=tail->next=p;
    		}
    		p->remainder-=g[i].gv;                   //装入后箱子的剩余体积
    		newg=(Goodslink *)malloc(sizeof(Goodslink));    //生成一个物品链
    		newg->gno=g[i].gno;
    		newg->link=NULL;
    		for(q=p->hg;q&&q->link;q=q->link);
    		if(!q)                //装入的物品是物品链的头结点
    			p->hg=newg;
    		else
    			q->link=newg;
    	}
    	return hbox;
    }
    
    //输出
    void PrintBox(Boxlink *h)
    {
    	int i=0;
    	Boxlink *p;
    	Goodslink *q;
    	for(p=h;p;p=p->next)
    	{
    		printf("第%d个箱子: ",++i);
    		for(q=p->hg;q;q=q->link)
    			printf("%5d",q->gno);
    		printf("\n");
    	}
    }
    
    
    
    int main(void)
    {
    //创建物品信息并初始化
    	ElemG *g;
        int i,w,n;   //w用于存放物品的体积
    	Boxlink *hbox;
    	printf("请输入物品的个数: ");
    	scanf("%d",&n);
        g=(ElemG *)malloc(n*sizeof(ElemG));
        for(i=0;i<n;i++)
    	{
    		g[i].gno=i+1;
    	    printf("请输入第%d个物品的体积: ",g[i].gno);
    	    scanf("%d",&w);
        	g[i].gv=w;
    	}
    
    
    //将所有物品按体积大小进行降序排列
    SortD(g,n);
    
    //装箱
    hbox=Packing(g,n);
    
    //输出
    PrintBox(hbox);
    return 0;
    }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

## 2）活动选择问题 ##

> 我是一个大帅哥，我很忙，需要参加各种活动，现在我需要一套算法，当我输入一天的行程，我需要这个算法告诉我，今天至少要取消多少个行程才能让每个日程之间时间不重叠。第一行输入今天的行程总数，接下来输入每个行程的时间段（如，8.0 10.0）。
> 
> 输入样例：
> 
> 10
> 
> 8.0
> 
> 10.0
> 
> 8.0
> 
> 10.0
> 
> 8.0
> 
> 10.0
> 
> 8.0
> 
> 10.0
> 
> 12.0
> 
> 14.5
> 
> 输出样例：
> 
> 3
> 
> **解题思路：在不与已选区间重叠的前提下，优先选择右端点最小的区间。按区间右端点排序后，依次检查，不重叠就选择，并更新已选区间的最右端，方便判断重叠。**

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+5;
    
    struct node{
    	int l,r;
    	void read()
    	{
    		static double _l,_r;
    		scanf("%lf%lf",&_l,&_r);
    		l=_l*100+0.5;
    		r=_r*100+0.5;
    	}
    	
    	bool operator<(const node &rhs)const{
    		return r<rhs.r;    //选择较小的右端
    	}
    }a[N];
    
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	n/=2;     //看右端
    	for(int i=0;i<n;++i)
    	{
    		a[i].read();  //读入数据
    	}
    	sort(a,a+n);        //排序
    	int right=-1,cnt=0;
    	for(int i=0;i<n;++i)
    	{
    		if(a[i].l>=right)      //更新已选区间的最右端
    		{
    			right=a[i].r;
    		}
    		else            //重复时，计数器加1
    		{
    			cnt++;
    		}
    	}
    	printf("%d",cnt);
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

## 3）库特君吃面条 ##

> 他将面条放在了数轴上，每根面条对应数轴上的两个点a和b（a<b），他想知道在任意两根面条不重叠（端点可以重叠）的情况下最多选出多少根面条。
> 
> 1<=n<=100
> 
> \-999<=a<b<=999
> 
> 输入描述：
> 
> 第一行一个整数N
> 
> 接下来，N行每行N个整数a和b
> 
> 输出描述：
> 
> 一个数的答案
> 
> 输入样例：
> 
>     3
>     -6 -3
>     1 3
>     2 5
> 
> 输出样例：
> 
> 2
> 
> 解题思路：同上

#include<bits/stdc++.h>
    using namespace std;
    const int N=100+5;
    const int inf=0x3f3f3f3f;
    
    struct node{
    	int l,r;
    	void read()
    	{
    		scanf("%d%d",&l,&r);
    		if(l>r)  swap(l,r);
    	}
    	bool operator < (const node &rhs) const
    	{
    		return r<rhs.r;
    	}
    }a[N];
    
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i=0;i<n;++i)
    	{
    		a[i].read();
    	}
    	sort(a,a+n);
    	int right=-1000,cnt=0;
    	for(int i=0;i<n;++i)
    	{
    		if(a[i].l>=right)
    		{
    			++cnt;
    			right=a[i].r;
    		}
    	}
    	printf("%d\n",cnt);
    	return 0;
    }

结果：

![20190816171926424.png][]

# 2 原理总结 #

> 贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点，它做出在当时看来最佳的选择。这种启发式策略并不保证总能找到最优解，但对于有些问题确实有效，如活动选择问题。

> 贪心算法的一般步骤：
> 
>  *  将最优化问题转化为这样的形式：对其作出一次选择后，只剩下一个子问题需要解决；
>  *  证明作出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的；
>  *  证明作出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就构成了最优子结构。

> 在贪心算法中，我们总能做出当时看来最佳的选择，然后求解剩余唯一的子问题。贪心算法进行选择时，可能依赖之前做出的选择，但不依赖任何将来的选择或是子问题的解。贪心算法在进行第一次选择之前不求解任何子问题。一个贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题的实例变得更小。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211109/4c26551927bd4607b282e7aae9d7ed21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211109/69a68c70dcf842519de8caf804047f86.png
[20190816171926424.png]: /images/20211109/50f276d5feda4e30badddce812227a78.png