问题描述：

用2台机器A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai≥bi，而对某些j，有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)。

数据输入：

由文件input.txt提供输入数据。文件的第一行是1个正整数n，表示要处理n个作业。左接下来的2行中，每行有n个正整数，分别表示机器A和机器B处理第i个作业需要的处理时间。

结果输出：

将计算的最短处理时间输出到文件output.txt。

input.txt
6
2 5 7 10 5 2
3 8 4 11 3 4

output.txt
15

#include <iostream>
#include <vector>
using namespace std;
#define MAXN 100010
/*
6
A:2 5 7 10 5 2 
B:3 8 4 11 3 4
最极端的情况下，所有任务都交给一台机器完成，则其完成的系列事件的事件最多为sum(a_i)或sum(b_i)。
设dp数组bool dp[i][j][k],表示前k个作业能否在处理机A总用时不超过i（i<=sum(a_i)），且在处理机B总用时不超过j(j<=sum(b_i))的情况下完成。 递推公式推导 1、假设第k个作业选择处理机A，则dp[i][j][k] = dp[i-a_k][j][k-1](i>=a_k)
2、假设第k个作业选择处理机B，则dp[i][j][k] = dp[i][j-b_k][k-1](j>=b_k)
3、综合考虑两种情况，则dp[i][j][k] = dp[i-a_k][j][k-1] || dp[i][j-b_k][k-1]；
   1.若dp[i-a_k][j][k-1]为true,则说明前k-1个作业可以在此之前完成，则其在此刻选择处理机A，也可以在dp[i][j][k]时刻完成；
   2.若dp[i][j-b_k][k-1]为true,则说明前k-1个作业可以在此之前完成，则其在此刻选择处理机B，也可以在dp[i][j][k]时刻完成；
   3.true||true = true, true||false = true, false||true = true, false||false = false。
4、遍历取出n对应的true，计算花费的最少时间。（每个true的x轴y轴较大的那个值的最小值）
*/

int n;//作业数
int a[MAXN], b[MAXN];//作业花费时间
vector<vector<vector > > dp;
int sum_a = 0, sum_b = 0;
void init(){
    cin>>n;
    for(int i=0;i<n;i++){ cin>>a[i];
        sum_a += a[i];
    }
    for(int i=0;i<n;i++){ cin>>b[i];
        sum_b += b[i];
    }
    dp = vector<vector<vector>>(sum_a + 1, vector<vector>(sum_b + 1, vector(n + 1, false)));//dp从作业数为0开始
    for(int i=0;i<=sum_a;i++){
        for(int j=0;j<=sum_b;j++){
            dp[i][j][0] = true;//若没有作业，则必可以完成
        }
    }
}

void solve(){
    for(int k=1;k<=n;k++){//遍历n个作业
        for(int i=0;i<=sum_a;i++){//遍历处理机A的总用时
            for(int j=0;j<=sum_b;j++){//遍历处理机B的总用时 if(i >= a[k-1]){//选择处理机A
                    dp[i][j][k] = dp[i-a[k-1]][j][k-1];
                }
                if(j >= b[k-1]){//选择处理机B
                    dp[i][j][k] = dp[i][j-b[k-1]][k-1] || dp[i][j][k];
                }
            }
        }
    }
}
void getOptimalTime(){
    int optimal_time = max(sum_a, sum_b);
    for(int i=0;i<=sum_a;i++){
        for(int j=0;j<=sum_b;j++){
            if(dp[i][j][n]){
                int tempOptimalTime = max(i, j);//选择处理机A或B的较大值
                if(tempOptimalTime < optimal_time){//更新最优时间
                    optimal_time = tempOptimalTime;
                }
            }
        }
    }
    cout<<optimal_time<<endl;
}

int main(){
    init();
    solve();
    getOptimalTime();
    return 0;
}
/*
6
2 5 7 10 5 2 
3 8 4 11 3 4
*/