c++中的贪心算法怎么实现

发布时间:2020-06-22 09:39:52 作者:Leah
来源:亿速云 阅读:780

这篇文章给大家分享的是c++中的贪心算法怎么实现,相信大部分人都还没学会这个技能,为了让大家学会,给大家总结了以下内容,话不多说,一起往下看吧。

c++中的贪心算法怎么实现

分治法、动态规划在此之前没有记录下来,学到贪心算法的时候,觉得需要总结一下学过的东西,也能更好的理解。动态规划的设计,要满足最优子结构性质和重叠子问题,采用自底向上的策略,计算出最优值,找到整体最优解。这个过程有时候挺难的,主要在写出递归式,要自底向上填表。贪心策略有点像动态规划,但在一些方面是不同的,有时候贪心算法的思想更容易想到。它要满足子问题最优而得到整体最优?两个条件:最优子结构性质和贪心选择性质。满足贪心选择性质一定满足最优子结构性质,而满足最优子结构性质不一定满足贪心选择性质,比如背包问题可以用贪心算法解决,而0-1背包问题只能用动态规划。

典型的贪心问题活动安排,有n个活动,给出开始时间和结束时间,要尽可能安排多的活动(时间互相不冲突)。解决这个问题正确的贪心思想是以每个活动结束时间为比较变量,按结束时间升序排好活动次序,接着就进行比较选择。而会场安排问题与活动又有些不同之处,下面是我的解题过程。

7-2 会场安排问题 (20 分)

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

输入格式:

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

输出格式:

输出最少会场数。

输入样例:

5
1 23
12 28
25 35
27 80
36 50

输出样例:

3
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//标记该活动是否被安排,0表示未安排,1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比较规则:以结束时间升序排列 
{ 
    return a.end<b.end;
 } 
int main()
{
    int i,j,n;
    node temp;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//总共需要的会场数量 
    for(i=0;i<n;i++)//方法2 
    {
        if(!t[i].flag)//找到未安排的活动,进行场地安排 
        {
            sum++;
            int p=i;
            for(j=p+1;j<n;j++)//当前活动结束时间与下一个活动开始不相交 ,则安排到同一个会场 
            {
                if(t[p].end<=t[j].begin&&!t[j].flag)
                {
                    p=j;t[j].flag=1;
                }
            }
            t[i].flag=1;
        }
    }
    cout<<sum;
    return 0;
}

贪心策略为:把尽可能多的时间互不冲突的活动安排到一个会场,若活动时间交叉,则在安排到另一个会场。

将所有活动按结束时间升序排列,利用sort函数,自定义cmp方法。循环体中,每次可以找到还没有安排的活动,并以这个活动搜索能同时容纳到一个会场的其他活动(这一步嵌套在内层循环中),经过两层循环,把所有活动全部安排好,这时也已经计算出需要的会场数量sum。

类似的问题是区间选点

7-10 选点问题 (15 分)

数轴上有n个闭区间[ai, bi]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)。

输入格式:

第一行一个数字n,表示有n个闭区间。 下面n行,每行包含2个数字,表示闭区间[ai, bi]

输出格式:

一个整数,表示至少需要几个点

输入样例:

在这里给出一组输入。例如:

3
1 3
2 4
5 6

输出样例:

在这里给出相应的输出。例如:2

开始想找出几个区间共同段,并且记录每个共同段中包含哪些区间,这样算出最少选点。后来发现觉得这个想法其实可以简化一下,策略为:以右端为挡板,看看前面是否包含其他区间,如果是,则不记数,反之,说明没有共同段,需要计数并且移动挡板位置继续寻找。贪心策略是选择区间右端点,保证能够包含更大交叉段,选的点最少。

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比较规则,按区间右端点升序排列 
{
    return a.r<b.r;
} 
int main()
{
    int n,i,j,count=1,select;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//预处理,将区间按规则排好序,方便后续比较 
    select=dots[0].r;
    //贪心策略是选择区间右端点,保证能够包含更大交叉段,选的点最少 
    for(i=1;i<n;i++)//每次将当前选择的一个区间的右端点与下一个(或者同一区间,可忽略)左端比较 
    {
        if(dots[i].l>select)//如果没有交叉,选点+1,并以此区间右端为新一轮比较的点 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<<count;
    return 0;
}

上述就是小编为大家分享的c++中的贪心算法的实现方法了,如果您也有类似的疑惑,不妨参照上述方法进行尝试。如果想了解更多相关内容,请关注亿速云行业资讯。

推荐阅读:
  1. 使用Python怎么实现一个贪心算法
  2. C++贪心算法实现活动安排问题(实例代码)

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

贪心算法 c++ c+

上一篇:MySQL中SQL_MODE的使用

下一篇:推荐系统冷启动解决方法

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》