动态规划：任务调度算法

 

有n个作业，a1,a2…..an，作业aj的处理时间为tj，产生的效益为pj，最后完成期限为dj，作业一旦被调度则不能中断，如果作业aj在dj前完成，则获得效益pj，否则无效益。给出最大化效益的作业调度算法。

Hulu的一道笔试题。
来源：

我们记作业处理时间为cost[],效益为value[],完成期限为deadline[]，总时间限制为time。

先来分析题目。题目变量很多，因为每个任务都只能被执行一次。直观感受应该是一个0-1背包问题。

首先我们先刨去完成期限不考虑。n个作业相当于n个物品，效益相当于每个物体的重量，处理时间则相当于物品的体积。我们有time长的时间可以运行，那么time就相当于背包的容量。这时，这就变成了一个典型的0-1背包问题。
再来回忆典型的0-1背包的处理。在背包容量为v的时候，我们决定对于一个物品i,是否可以放入的条件是v容量足以放下物品i以及前置物品。同样的，回到这道题目，在t时间点时，我们决定是否能将一个任务i加入到序列中，条件是t足够完成任务i和其前置任务,任务之外，还要考虑，在加入任务i后，完成的时间不能超过任务i的最后期限。

f[i][t]表示前i件任务在t时间段内执行可以获得的最大价值，参照基本的0-1背包的状态转移方程，有：
在不考虑完成期限时，其状态转移方程是：
        f[i][t] = max{f[i-1][t], f[i-1][t-cost[i]] + value[i]}
在考虑完成期限时，其状态转移方程是：
        f[i][t] = max{f[i-1][t],  (f[i-1][t-cost[i]] + value[i]|t<=deadline[i])}

示例代码如下。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int tasks = 2;
    int time = 10;
        //-1为占位符
    int cost[] = {-1,1,4};
    int value[] = {-1,10,6};
    int deadline[] = {-1,5,4};
    int maxvalue = 0;

    int tmp[tasks+1][time+1];
    memset(tmp, 0, sizeof(int)*(tasks+1)*(time+1));

    int task = 1;
    for(;task<=tasks;task++){
                int t;
        for(t=1;t<=time;t++){
            if(t>deadline[task])
                continue;
            if(t>=cost[task]){
                tmp[task][t] = tmp[task-1][t];
                if((tmp[task-1][t-cost[task]+1] + value[task])> tmp[task][t])
                    tmp[task][t] = tmp[task-1][t-cost[task]+1] + value[task];
                printf("%d %d = %d  n", task, t, tmp[task][t]);
                maxvalue = maxvalue<tmp[task][t]? tmp[task][t]:maxvalue;
            }
        }
    }

    printf("max = %d n", maxvalue);
}