贪心算法 订阅
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解 [1]  。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。也就是说,不从整体最优上加以考虑,做出的只是在某种意义上的局部最优解 [1]  。 展开全文
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解 [1]  。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。也就是说,不从整体最优上加以考虑,做出的只是在某种意义上的局部最优解 [1]  。
信息
别    称
贪婪算法 [1]
领    域
数理科学 [1]
定    义
做出在当前看来是最好的选择 [1]
中文名
贪心算法 [1]
核    心
根据题意选取一种量度标准
外文名
greedy algorithm [1]
贪心算法算法思路
贪心算法一般按如下步骤进行: [2]  ①建立数学模型来描述问题 [2]  。②把求解的问题分成若干个子问题 [2]  。③对每个子问题求解,得到子问题的局部最优解 [2]  。④把子问题的解局部最优解合成原来解问题的一个解 [2]  。贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯 [2]  。
收起全文
精华内容
参与话题
问答
  • 贪心算法

    千次阅读 多人点赞 2019-04-07 15:16:00
    贪心算法贪心算法的定义贪心算法解决问题算法流程 贪心算法的定义 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上...

    贪心算法的定义

    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

    贪心算法解决问题

    (1)你有n堆石头质量分别为W1,W2,W3…Wn.(n<=100000)现在需要你将两堆石头合并,问一共所用力量最小是多少?
    例如:
    n=4;
    3,1,7,5;
    解题思路:每次挑重量最少的两堆石头,直到所有石头挑完。
    如例题,先将三堆石头按照重量从小到大排序为:1,3,5,7。第一次所用最小力量为1+3=4;然后将4,5,7按从小到大排序,第二次所用最小力量为4+5=9;然后将9,7按从小到大排序,为7,9,第三次所用最小力量为7+9=16;所以一共所用最小力量:4+9+16=29.

    #include<stdio.h>
    typedef struct stone
    {
        int num;
    }Stone;
    Stone st[100];
    void sort(int start_flag,int n)//对n堆石头质量按照从小到大的顺序排序
    {
        int i,j;
        Stone temp;
        for(i=start_flag;i<n-1;i++)
            for(j=start_flag;j<n-1-i;j++)
            if(st[j].num>st[j+1].num)
        {
            temp=st[j];
            st[j]=st[j+1];
            st[j+1]=temp;
        }
    }
    void main()
    {
        int n,i,count=0,start_flag=0;
        printf("输入石头堆数:");
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&st[i].num);
        for(i=start_flag;i<n-1;i++)
        {
            sort(start_flag,n);
            st[i+1].num+=st[i].num;
            count+=st[i+1].num;
            start_flag++;
        }
        printf("一共所用最少力量%d \n",count);
    }
    

    (2)公司的会议室每天都会有许多会议,有时这些会议的计划时间会发生冲突,需要选择出一些会议。小刘的工作就是安排公司会议室的会议,每个时间最多安排一个会议。现在小刘有一些会议计划的时间表,他想尽可能的安排更多的会议,请问他该如何安排。
    输入
    第一行输入一个整数n(1<n<10000)表示该测试数据共有n个活动。
    随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi<=Ei)
    输出
    输出最多能够安排的会议数量,以及哪些会议被安排。
    样例输入
    3
    1 10
    10 11
    11 20
    样例输出
    最多能够安排的会议数量:2
    安排的会议分别为:
    第1个会议.第3个会议.

    #include<stdio.h>
    typedef struct meet
    {
        int begin;
        int end;
        int flag;
    
    } Meet;
    Meet mt[10000];
    void sort(int n)//根据每场会议的结束时间排序
    {
        int i,j;
        Meet temp;
        for(i=0; i<n-1; i++)
            for(j=0; j<n-1-i; j++)
                if(mt[j].end>mt[j+1].end)
                {
                    temp=mt[j];
                    mt[j]=mt[j+1];
                    mt[j+1]=temp;
                }
    }
    void main()
    {
        int n,i,j,count=1;
        printf("输入会议数:");
        scanf("%d",&n);
        for(i=0; i<n; i++)
            scanf("%d %d",&mt[i].begin,&mt[i].end);
        sort(n);
        i=0;
        mt[0].flag=1;
        for(j=1; j<n; j++)
        {
            if(mt[j].begin>mt[i].end)
            {
                mt[j].flag=1;
                count++;
                i++;
            }
        }
        printf("\n最多能够安排的会议数量:%d \n",count);
        printf("安排的会议分别为:\n");
        for(i=0; i<n; i++)
            if(mt[i].flag==1)
                printf("第%d个会议.",i+1);
    }
    
    

    算法流程

    Created with Raphaël 2.2.0开始找到贪心的点,按贪心的点排序可选择?结束yesno
    展开全文
  • 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法

空空如也

1 2 3 4 5 ... 20
收藏数 24,586
精华内容 9,834
关键字:

贪心算法