小明可以同时做计算两道不同的题目
习题集包含n道题目，没到题目耗时nums[i]，求最少需要时间
1. 动态规划
题目等价于将数组划分为两个和最接近的数组，求两数组和的最大值
int maxval(vector<int> &nums){ //尝试划分为两个最接近的数组，同时返回两数组和的最大值
int n = nums.size();
int sum = accumulate(nums.begin(),nums.end(),0);
int diff = sum;//两数组差值
int res = sum;//两数组和的最大值
vector<bool> dp(sum+1);//记录能否凑成相应数
dp[0] = true;
for(int i=0;i<n;i++)
for(int j=sum;j>=nums[i];j--){
dp[j] = dp[j]|dp[j-nums[i]];
if(dp[j]&&abs(sum-2*j)<diff){
diff = abs(sum-2*j);//更新差值
res = max(j,sum-j);
}
}
return res;
}