站点图标 陌路寒暄

独立任务最优调度问题

code

独立任务最优调度问题

时间： 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;
}

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

退出移动版