[ 算法 ] 独立任务最优调度问题

问题

两台处理器A和B处理n个任务，第i个任务在处理器A上处理需要时间ai，在处理器B上处理需要时间bi。由于处理器性能不同，ai和bi不一定相等。

两台处理器可以同时开机处理任务。一个作业只需要由一个处理处理完毕即可，并且不存在单一任务分成两部分由两台处理器同时处理的情况，也不存在一台处理器同时处理2个或者更多任务的情况。

给定n个任务的处理时间，试进行任务划分，使得两台处理器处理这些任务的时间最短。当某台处理器开始启动时开始计时，到所有处理器都关机停止计时。

代码

#include <stdio.h>  
int main()
{
    int n;
    int* a, * b, * t;
    int i, k;
    int sa = 0;
    int result = 1000000;
    scanf("%d", &n);
    a = new int[n];
    b = new int[n];
    for (i = 0; i < n; i++) {
        scanf("%d", a + i);
        sa = sa + *(a + i);
    }
    t = new int[sa + 1];
    for (i = 0; i <= sa; i++)
        t[i] = 0;
    for (i = 0; i < n; i++)
        scanf("%d", b + i);
    for (k = 0; k < n; k++) {
        for (i = sa; i >= 0; i--) {
            if (i >= a[k])
                t[i] = t[i] + b[k] < t[i - a[k]] ? t[i] + b[k] : t[i - a[k]];
            else
                t[i] = t[i] + b[k];
        }
    }
    for (i = 0; i <= sa; i++)
    {
        k = i > t[i] ? i : t[i];
        if (result > k)
            result = k;
    }
    printf("%d\n", result);
    return 0;
}  #define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>  
int main()
{
    int n;
    int* a, * b, * t;
    int i, k;
    int sa = 0;
    int result = 1000000;
    scanf("%d", &n);
    a = new int[n];
    b = new int[n];
    for (i = 0; i < n; i++) {
        scanf("%d", a + i);
        sa = sa + *(a + i);
    }
    t = new int[sa + 1];

    for (i = 0; i <= sa; i++)
        t[i] = 0;
    for (i = 0; i < n; i++)
        scanf("%d", b + i);

    //遍历每一个任务
    for (k = 0; k < n; k++) {
        //以a的总处理时间来进行任务调度
        for (i = sa; i >= 0; i--) {

            if (i >= a[k])//当前任务需要的时间能否被a处理
                //当a的任务的处理任务所用的时间比b的小(b处理该任务耗时比a小)则由b来执行此任务
                t[i] = t[i] + b[k] < t[i - a[k]] ? t[i] + b[k] : t[i - a[k]];
            else
                //将该任务交给b来处理
                t[i] = t[i] + b[k];
        }
    }
    for (i = 0; i <= sa; i++)
    {
        //找出a b所有的最大处理时间(找出所有处理时间最大的值，如果时间太短的会导致任务无法被处理)
        k = i > t[i] ? i : t[i];

        printf("i= %d , t[%d]= %d , k =%d \n", i, i, t[i], k);
        //在最大的处理时间中找出处理最小的处理时间
        if (result > k)
            result = k;
    }
    printf("%d\n", result);
    return 0;
}#include <stdio.h>
int main()
{
    int n;
    int* a, * b, * t;
    int i, k;
    int sa = 0;
    int result = 1000000;
    scanf("%d", &n);
    a = new int[n];
    b = new int[n];
    for (i = 0; i < n; i++) {
        scanf("%d", a + i);
        sa = sa + *(a + i);
    }
    t = new int[sa + 1];
    for (i = 0; i <= sa; i++)
        t[i] = 0;
    for (i = 0; i < n; i++)
        scanf("%d", b + i);
    for (k = 0; k < n; k++) {
        for (i = sa; i >= 0; i--) {
            if (i >= a[k])
                t[i] = t[i] + b[k] < t[i - a[k]] ? t[i] + b[k] : t[i - a[k]];
            else
                t[i] = t[i] + b[k];
        }
    }
    for (i = 0; i <= sa; i++)
    {
        k = i > t[i] ? i : t[i];
        if (result > k)
            result = k;
    }
    printf("%d\n", result);
    return 0;
}