贪心算法

• 贪心算法的定义
• • 贪心算法解决问题
  • 算法流程

贪心算法的定义

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

贪心算法解决问题

(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