任务调度问题---算法导论

任务调度问题就是给定一个有穷单位时间任务的集合S，集合S中的每个任务都有一个截止期限di和超时惩罚wi，需要找出集合S的一个调度，使得因任务误期所导致的总惩罚最小，这个调度也称为S的一个最优调度。

#include 
#include 

void swap（int *x int *y）
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
/*任务调度算法满足拟阵性质，利用GREEDY贪心策略*/
/*期限序列d[] d1d2……dn*/
/*惩罚序列w[] w1w2……wn*/
/*任务个数n*/
void taskSchedule（int *d int *w int n）
{
    int i = 0;
    int j = 0;
    int k = 1;                                    //用于指示数组a[]
    int s = 0;
    int t = 1;                                    //用于指示数组b[]
    int a[n+1];                                 //存放任务调度序列
    int b[n+1];                                //存放在贪心选择中未被选的任务序列
    int sn[n+1];                               //存放惩罚递减序列编号
    int flag = 0;                               //0表示当前集合满足独立性，1表示不满足独立性
    int count = 0;                           //表示任务序列中期限为t或更早的任务个数
    memset（a 0 sizeof（a））;
    memset（b 0 sizeof（b））;
    for（i = 0; i <= n; i++）
    {
        sn[i] = i;
    }
    //按照惩罚递减排序 sn[]存放排序后的任务编号
    for（i = 1; i < n; i++）
    {
        for（j = i + 1; j <= n; j++）
        {
            if（w[sn[i]] <= w[sn[j]]）
            {
                swap（&sn[i] &sn[j]）;
            }
        }
     }
     k = 1;
     //for（i=1;i<=n;i++） printf（“%d  “w[sn[i]]）;
     //将最小化迟任务的惩罚之和转化为最大化早任务的惩罚之和，即尽量让具有大惩罚的任务在期限内完成。
     //a[]存放已选择的任务序列，b[]存放未被选择的任务序列
     for（i = 1; i <= n; i++）
     {
         //尝试加入任务，判断独立性
         flag = 0;
         a[k] = sn[i];
         for（j = 1; j <= k; j++）//表示当前的t
         {
             count = 0;
             for（s = 1; s <= k; s++）//求当前序列a[]中期限<=t的任务个数
             {
                 if（d[a[s]] <= j） count++;
             }
             if（count > j）
             {
                 flag = 1;
                 break;
             }
         }
         if（flag == 1）//表示加入任务后，集合不具有独立性，即在期限t需完成的任务>t
         {
             b[t] = sn[i];
             a[k] = 0;
             t++;
         }
         else
         {
             k++;
         }
     }
     //消除最后的无效编号
     if（b[t] == 0） t--;