算法导论-任务调度问题

问题描述：

在单处理器上具有期限和惩罚的单位时间任务调度问题（课本P239）

实验要求：

（1）实现这个问题的贪心算法

（2）将每个 wi 替换为max{m1,m2…mn}—wi，运行算法比较结果。

解题思路：

1.先将任务按照时间惩罚递减顺序进行排序，

2.然后用贪心的思想，尽量把惩罚重的任务先放入待完成队列中。

这里我是用了一个fla数组进行标记的，先试着把任务期限为d的任务放入fla数组的第d个位置上，若该位置为1，说明这个位置已经被使用了，那么往前面进行查找，看在完成期限之前，有没有空的位置可以放进去。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <cstring>
using namespace std;
#define n 6
typedef struct{
    int id;
    int d;
    int w;
}task;
bool cmpW(task t1,task t2){
    return t1.w>t2.w;
}
bool cmpD(task t1,task t2){
    return t1.d<t2.d;
}
void random_init(task t[]){
    srand((unsigned)time(NULL));
    for(int i=;i<n;i++){
        t[i].id=i+;
        t[i].d=rand()%n+;
        t[i].w=rand()%30;
    }
}
void copy(task &t1,task &t2){
    t1.id=t2.id;
    t1.d=t2.d;
    t1.w=t2.w;
}
int greedy(task a[],task ta[],int &ans){
    int num=,i,j;//当前已经完成的任务数量
    sort(ta,ta+n,cmpW);
    int fla[];
    memset(fla,,sizeof(fla));
    for(i=;i<n;i++){
        for(j=ta[i].d;j>;j--){
            if(fla[j]==){
                fla[j]=;
                break;
            }
        }
        if(j>){
            copy(a[num++],ta[i]);
            ans-=ta[i].w;
        }
    }
    return num;
}
int main()
{
    task ta[n],a[n];
    printf("正在随机生成n(%d)组数据...\n",n);
    random_init(ta);
    printf("生成的数据为:\n");
    int ans=,maxx=-;
    for(int i=;i<n;i++){
        printf("ID：%d，期限：%d，惩罚：%d\n",ta[i].id,ta[i].d,ta[i].w);
        ans+=ta[i].w;
        if(ta[i].w>maxx)
            maxx=ta[i].w;
    }
    int k=greedy(a,ta,ans);
    printf("任务惩罚为：%d\n",ans);
    sort(a,a+k,cmpD);
    printf("将完成执行的任务按照时间递增顺序排列输出：\n");
    for(int i=;i<k;i++){
        printf("ID：%d，期限：%d，惩罚：%d\n",a[i].id,a[i].d,a[i].w);
    }

    //若将每个wi替换为max{m1,m2...mn}—wi，改变惩罚值再求一次
    ans=;
    for(int i=;i<n;i++){
        ta[i].w=maxx-ta[i].w;
        ans+=ta[i].w;
    }
    printf("\n改变惩罚值后输出各任务数据\n");
    for(int i=;i<n;i++){
        printf("ID：%d，期限：%d，惩罚：%d\n",ta[i].id,ta[i].d,ta[i].w);
    }
    k=greedy(a,ta,ans);
    printf("改变惩罚值后的任务惩罚为：%d\n",ans);
    sort(a,a+k,cmpD);
    printf("将完成执行的任务按照时间递增顺序排列输出：\n");
    for(int i=;i<k;i++){
        printf("ID：%d，期限：%d，惩罚：%d\n",a[i].id,a[i].d,a[i].w);
    }
    return ;
}
           

测试运行结果如下：