独立任务最优调度问题

独立任务最优调度问题

时间: 1ms        内存:64M

描述:

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间 ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai≥bi,而对于某些j,j≠i,有aj<bj。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理2个作业。设计一个动态规划算法,使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例: (a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)。

对于给定的2 台处理机A和B处理n个作业,找出一个最优调度方案,使2台机器处理完这n个作业的时间最短。

输入:

输入数据的第1行是1个正整数n(n≤200), 表示要处理n个作业。接下来的2行中,每行有n个正整数,分别表示处理机A和B处理第i个作业需要的处理时间。每台机器总的工作时间最大不会超过 10000。

输出:

输出只有一个整数,表示计算出的最短处理时间。

示例输入:

6
2 5 7 10 5 2
3 8 4 11 3 4

示例输出:

15

提示:

参考答案(内存最优[1900]):

#include<iostream>
#include<cstring>
#include<malloc.h>
using namespace std;
int task_schedule(int *a,int *b,int n)
{
    int i,j;
    int sa=0;
    for(i=0; i<n; i++)
        sa+=a[i];
    int **t=(int **)malloc(sizeof(int*)*(n+1));
    for(j=0; j<=n; j++)
    {
        t[j]=(int *)malloc(sizeof(int)*(sa+1));
        memset(t[j],0,sizeof(int)*(sa+1));
    }
    for(int k=1; k<=n; k++)
    {
        for(i=0; i<=sa; i++)
        {
            if(i<a[k-1])
                t[k][i]=t[k-1][i]+b[k-1];
            else t[k][i]=t[k-1][i-a[k-1]]>=(t[k-1][i]+b[k-1])?(t[k-1][i]+b[k-1]):t[k-1][i-a[k-1]];
        }
    }

    int min=1<<30;//相当于1X2^30,此数非常的大
    for(i=0; i<=sa; i++)
    {
        int tmp=t[n][i]>i?t[n][i]:i;
        if(tmp<min)
            min=tmp;
    }

    return min;
}

int main()
{
    int n;
    int i;
    cin>>n;
    int *a=new int[n];
    int *b=new int[n];
    for(i=0; i<n; i++)
        cin>>a[i];
    for(i=0; i<n; i++)
        cin>>b[i];
    int res=task_schedule(a,b,n);
    cout<<res<<endl;
}

参考答案(时间最优[3]):

#include<iostream>
#include<cstring>
#include<malloc.h>
using namespace std;
int task_schedule(int *a,int *b,int n)
{
    int i,j;
    int sa=0;
    for(i=0; i<n; i++)
        sa+=a[i];
    int **t=(int **)malloc(sizeof(int*)*(n+1));
    for(j=0; j<=n; j++)
    {
        t[j]=(int *)malloc(sizeof(int)*(sa+1));
        memset(t[j],0,sizeof(int)*(sa+1));
    }
    for(int k=1; k<=n; k++)
    {
        for(i=0; i<=sa; i++)
        {
            if(i<a[k-1])
                t[k][i]=t[k-1][i]+b[k-1];
            else t[k][i]=t[k-1][i-a[k-1]]>=(t[k-1][i]+b[k-1])?(t[k-1][i]+b[k-1]):t[k-1][i-a[k-1]];
        }
    }

    int min=1<<30;//相当于1X2^30,此数非常的大
    for(i=0; i<=sa; i++)
    {
        int tmp=t[n][i]>i?t[n][i]:i;
        if(tmp<min)
            min=tmp;
    }

    return min;
}

int main()
{
    int n;
    int i;
    cin>>n;
    int *a=new int[n];
    int *b=new int[n];
    for(i=0; i<n; i++)
        cin>>a[i];
    for(i=0; i<n; i++)
        cin>>b[i];
    int res=task_schedule(a,b,n);
    cout<<res<<endl;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注