A17483. 平衡运输
填空题
困难
知识点
题目描述
平衡运输
题目描述
远古遗迹中发掘出了 n 件魔力核心，第 i 件核心蕴含的能量为 ki。
为了安全运输，需要将这些核心分配到两个不同的能量舱（记为舱 A 和舱 B）中。
每件核心必须整个放入一个舱，不可拆分。
分配完成后，设舱 A 的总能量为 sa，舱 B 的总能量为 sb。
为了平衡运输风险，希望两个舱中总能量较大的一方尽可能小，即最小化 max(sa,sb)。
请你计算这个最小的最大值。
输入格式
第一行，一个整数 n。
第二行，n 个整数 k1,k2,…,kn。
输出格式
输出一个整数，表示 max(sa,sb) 的最小可能值。
输入样例#1
5
2 3 5 10 12输出样例#1
17输入样例#2
6
22 25 26 45 22 31输出样例#2
89说明提示
2≤n≤20
1≤ki≤108
参考答案
#include<iostream>
int N;
int A[20];
int S = 0;
int solve(int i, int sum)
{
if (i == N)
{
return std::max(sum, S - sum);
}
else
{
auto pick = solve(i + 1, sum + A[i]);
auto drop = solve(i + 1, sum);
return std::min(pick, drop);
}
}
int main()
{
std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
S += A[i];
}
std::cout << solve(0, 0) << "\n";
}
上一题
下一题