问题描述

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要的时间ai，若由机器B来处理，则需要时间Bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai >= bi，而对于某些j，j != i，有aj < bj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总时间）。

输出输出示例

数据输入：第一行是1个正整数n，表示要处理的n个作业；在接下来的2行中，每行有n个正整数，分别表示处理机A和B处理第i个作业需要的处理时间。
结果输出：输出计算出的最短处理时间。

输入：

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

输出：

15

算法分析

这个问题其实可以看成一种0-1背包问题，对于每一个作业都有两种选择，一种是交给A处理机做，一种是不交给A处理机做（即交给B处理机做），每次选择一个作业，都把它给A做还是给B做的所有情况列出来，最后取A时间和B时间中的最大值即为每一个情况需要的时间，再从中取最小值计算出最短处理时间。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110, M = 10010;
int a[N], b[N], dp[N][M], suma, n;  


int main()
{
    scanf("%d",&n);

    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++)
        scanf("%d", &b[i]);

    for(int i = 1; i <= n; i ++){               //遍历每个作业
        suma += a[i];
        for(int j = 0; j <= suma; j ++){        //遍历每个作业处理机A用时为时的情况
            dp[i][j] = dp[i-1][j] + b[i];       //先把作业分配给B
            //当A可以处理此作业之后每次都取给A做或者给B做后B的最小时间
            if(j >= a[i]) dp[i][j] = min(dp[i-1][j]+b[i], dp[i-1][j-a[i]]);
        }
    }
    int ans = dp[n][0];                     //最优值初始化
    for(int i = 1; i <= suma; i ++){
        int maxans = max(dp[n][i], i);      //取A和B的最大值记为处理时间
        ans = min(ans, maxans);             //取处理时间的最小值
    }
    printf("%d", ans);
    return 0;
}