描述
将一个数组分成两部分，使这两部分的和之差最小，求这个最小差值
分析
这题是一道非常经典的选数问题，思路是在一个数组中选一些数，使这些数的和在不大于数组元素总和一半 的前提下尽可能大。
首先这一题我优先想到的解法是 背包，开一个长度为
的数组滚动求解，时间复杂度
，空间复杂度
，但是在这一题中，
的值可以达到非常大，我们开不了那么大的空间，所以并不合适。
注意到 的范围很小，所以可以采取暴力搜索的办法，可以根据
的值进行剪枝优化，时间复杂度
，空间复杂度
代码
// 分苹果问题
#include <cstdio>
typedef long long ll;
int a[25], n;
ll sm, ans;
void dfs(int cur, ll val) { // 第二个参数类型必须设为长整型，否则容易出错
if (val * 2 > sm) return;
if (cur == n) {
if (val > ans) ans = val; // 剪枝优化
return;
}
dfs(cur + 1, val + a[cur]);
dfs(cur + 1, val);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sm += a[i];
}
dfs(0, 0);
printf("%lld\n", sm - ans - ans);
return 0;
}
