问题标题: 酷町堂：贪心

所谓的“贪心算法”，就是每一次面临选择时，选择最优、最先、最X的一项，反正就是突出一个“最”字。比如有1，4，3，2，让你选两个数，令选出来的数最大，你肯定按照每次选择都选择，剩余数中最大的一个数，第一次选择4，剩下还有1，3，2，这时傻子都会选择3啊，从而得出在1，4，3，2这四个数中，选出的两数和是最大的。此时，你就不知不觉地运用到了贪心算法，以最大选择为贪心。

那么，“贪心算法”真正用到编程中是如何呢？下面用一道2013上半年软件设计师的软考题来说明这个问题。

题目是这样的：

设有M台完全相同的机器运行N个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。假设任务已经按照其运行的时间从大到小来排序，算法基于最长运行时间作业优先的策略：按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。

这里要求定义的变量如下，所有数组的下标皆从0开始：

设，m是机器数，n是任务数，t[]的长度为n，其中每个元素表示任务的运行时间。s[][]长度为mn，下标从0开始，其中s[i][j]表示机器i运行的任务j的编号。d[]长度为m，其中匀速d[i]表示机器i运行的时间，count[]长度为m，其中元素count[i]表示机器i运行的任务数。max为完成所有任务的时间。min,i,j,k为临时定义变量，无意义。

考虑实例m=3（编号0-2），n=7（编号0-6)，各任务的运行时间为{16,14,6,5,4,3,2}（这里其实就是指t[i]定义为{16,14,6,5,4,3,2}，题目没有说）则求各个机器上的运行任务，从任务开始运行到完成所需要的时间。

这道题目，非常长，看起来非常让人头晕，实际上，根本一点都不难。如果你还学过《操作系统》的话，就更简单的。

意思就是将{16,14,6,5,4,3,2}这些数字扔到3个数组里面，使最终，这3个数组里面的数据之和的最大的一个，最小。你也可以想像倒水到3个杯子，要求你每次倒的水的多少只能从{16,14,6,5,4,3,2}这7个数字选一个，必须倒水倒7次，也就是这7个数字选完，最终尽可能让任一一个杯子都不溢出。

你当然是平均化倒水啊，每次倒水的时候，看哪个杯子水量最小倒哪个啊！

这时，就运用到所谓的“贪心算法”了。

最后求出来的结果是17。顺理成章就得到如下的代码，每一次选择都会有一个求最小值的过程：

#include<stdio.h>
void schedule(int m,int n,int *t){
    //初始化
    int i,j,k,max=0;
    int d[100],s[100][100],count[100];
    for(i=0;i<m;i++){
        d[i]=0;
        for(j=0;j<n;j++){
            s[i][j]=-1;//-1代表不执行任何任务，不与第0号任务混淆
        }
    }
    //分配前m个任务
    //必然是每个机器先分别接受1个任务
    for(i=0;i<m;i++){
        s[i][0]=i;
        d[i]=d[i]+t[i];
        count[i]=1;
    }
    //之后判断哪个机器任务耗时最少，让其接受任务
    //尽可能地并行，平均分配任务
    for(i=m;i<n;i++){
        int min=d[0];
        k=0;
        for(j=1;j<m;j++){//确定空闲机器，实质是在求当期任务总时间最少的机器
            if(min>d[j]){
                min=d[j];
                k=j;//机器k空闲
            }
        }
        s[k][count[k]]=i;//在机器k的执行队列添加第i号任务
        count[k]=count[k]+1;//机器k的任务数+1
        d[k]=d[k]+t[i];//机器k的任务执行时间+t[i]，也就是+第i号任务的耗时        
    }
    
    for(i=0;i<m;i++){//确定完成所有任务需要的时间，实质是求分配完所有任务之后，耗时最多的机器
        if(max<d[i]){
            max=d[i];
        }            
    }
    printf("完成所有任务需要的时间：%d\n",max);
    printf("各个机器执行的耗时一览：\n");
    for(i=0;i<m;i++){
        printf("%d:",i);
        for(j=0;j<n;j++){
            if(s[i][j]==-1){
                break;
            }
            printf("%d\t",t[s[i][j]]);
        }
        printf("\n");
    }
}
void main(){//测试用例
    int time[7]={16,14,6,5,4,3,2};
    schedule(3,7,time);    
}

最终运行结果如下：

这里，原题目还要对上述代码进行，除去初始化、打印那两步，算法核心的时间复杂度的分析。这个很好求的，不算初始化、打印那两步，分配前m个任务，一个for循环，终止于i<m，这里复杂度为m，之后判断哪个机器任务耗时最小，两层for循环，外层终结于i<m，里层为i<n，因此为mn，最后确定所有任务需要的时间，一个for循环，终止于i<m，这里复杂度为m，也就是m+mn+m，最高维度，用现在的话来说，就是最高次元为mn，因此mn+2m~mn（此乃高等数学的内容，不会面壁去~），也就是时间复杂度为O(mn)。

然而，实际上，由于贪心算法每一次选择都要找一个最优项，遍历数组的每一项都出现一个排序，不像这里一上来就已知一个排好顺序的数组，因此时间复杂度往往是O(n2)，而要是这题给出的数组没有排好序，估计要去到O(m2n2)了。

~~~~~~~~~~~~~~~~~我是分界线~~~~~~~~~~~~~~~~~~~~~~

望采纳，谢谢！~~