贪心算法

贪心算法

贪心算法的定义

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

贪心算法解决问题

(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 开始 找到贪心的点,按贪心的点排序 可选择? 结束 yes no

    原文作者:飞天程序猿
    原文地址: https://blog.csdn.net/li__ly/article/details/89058593
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞