3503. 数组划分（上海交通大学考研机试题）

3503. 数组划分

⭐️难度：简单 ⭐️类型：DFS

📖题目：题目链接 一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组的各元素之和 a,b的差最小。

输入格式 共一行，包含若干个正整数，表示给定数组。

输出格式 以降序的顺序，输出两个子数组的各元素之和。

数据范围 给定数组的元素个数范围 [2,1000]。 给定数组的元素取值范围 [1,1000000]。

输入样例：

10 20 30 10 10

输出样例：

40 40

🌟思路： 1️⃣首先利用一点小小的数学，计算diff：

不理解的话举一个极端的例子，sum=100，sa=sum/2=50,这样的话sb=sum-sa=50，sb-sa就是最小的，等于0。

2️⃣DFS过程：

一开始，我们让a集合为空，一个一个元素地加入a集合中，

• 不加入，直接考虑下一个元素加不加入，也就是继续递归；
• 加入，a集合之和加入arr[pos]，重新计算diff，如果更小就替换掉原来的diff，然后再继续递归考虑下一个元素加不加入a集合；

void DFS(vector<int> &arr,int pos,int sa) {
if (pos == arr.size()) {
return;
}
// arr[pos] 不放入 a集合 中
DFS(arr, pos + 1, sa);
// arr[pos] 放入到 a集合 中
int newdiff; // 记录当前的差值
if (2 * (sa + arr[pos]) – sum > 0) {
newdiff = 2 * (sa + arr[pos]) – sum;
}
else {
newdiff = sum – 2 * (sa + arr[pos]);
}

if (newdiff < diff) {
diff = newdiff;
}

DFS(arr, pos + 1, sa + arr[pos]);
}

3️⃣ 输出时利用一点数学：

// sa + sb = sum
// sb – sa = diff
int sa = (sum – diff) / 2;
int sb = sa + diff;
printf("%d %d\\n", sb, sa);

4️⃣（难想）剪枝： 但如果只是这样做时间复杂度会很高，所以考虑一下剪枝：

提前终止的情况：

1、总和为奇数时，最小差值只能是 1（如总和 15，7 和 8 差 1）； 2、选这个元素会让sa直接超过sum/2，差值只会变大

📚题解： 不剪枝：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<vector> // vector不需要.h
#include<list>
#include<set> // // 可以用 set 和 multiset
#include<unordered_set> // 可以用 unordered_set 和 unordered_multiset
#include<map> // 可以用 map 和 multimap
#include<unordered_map> // 可以用 unordered_map 和 unordered_multimap
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>
#include<stack>

using namespace std;

int sum = 0; // 记录数组的和
int diff = 0; // 记录遍历过程最小的差值

void DFS(vector<int> &arr,int pos,int sa) {
if (pos == arr.size()) {
return;
}
// arr[pos] 不放入 a集合 中
DFS(arr, pos + 1, sa);
// arr[pos] 放入到 a集合 中
int newdiff; // 记录当前的差值
if (2 * (sa + arr[pos]) – sum > 0) {
newdiff = 2 * (sa + arr[pos]) – sum;
}
else {
newdiff = sum – 2 * (sa + arr[pos]);
}

if (newdiff < diff) {
diff = newdiff;
}

DFS(arr, pos + 1, sa + arr[pos]);
}

int main() {
vector<int> arr;
int i;
while (scanf("%d", &i) != EOF) {
arr.push_back(i);
}
for (int i = 0;i < arr.size();i++) {
sum += arr[i];
}
diff = sum; // 初始差值等于sum
DFS(arr, 0, 0);

// sa + sb = sum
// sb – sa = diff
int sa = (sum – diff) / 2;
int sb = sa + diff;
printf("%d %d\\n", sb, sa);
return 0;
}

剪枝后：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<vector> // vector不需要.h
#include<list>
#include<set> // // 可以用 set 和 multiset
#include<unordered_set> // 可以用 unordered_set 和 unordered_multiset
#include<map> // 可以用 map 和 multimap
#include<unordered_map> // 可以用 unordered_map 和 unordered_multimap
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>
#include<stack>

using namespace std;

int sum = 0; // 记录数组的和
int diff = 0; // 记录遍历过程最小的差值
bool exitflag = false; // 记录是否要提前退出

void DFS(vector<int> &arr,int pos,int sa) {
if (pos == arr.size() || exitflag == true) {
return;
}
// 优化2：优先处理a集合加入arr[pos]
// arr[pos] 放入到 a集合 中
int newdiff; // 记录当前的差值
if (2 * (sa + arr[pos]) – sum > 0) {
newdiff = 2 * (sa + arr[pos]) – sum;
}
else {
newdiff = sum – 2 * (sa + arr[pos]);
}

if (newdiff < diff) {
diff = newdiff;
// 提前退出的情况
if (diff == 0 | diff == 1 || 2 * arr[pos] > sum) {
exitflag = true;
}
}

// 优化3：sa<sb才继续递归
if (2 * (sa + arr[pos]) – sum < 0 ) {
DFS(arr, pos + 1, sa + arr[pos]);

}

// arr[pos] 不放入 a集合 中
DFS(arr, pos + 1, sa);
}

bool compare(int lhs, int rhs) {
return lhs > rhs;
}

int main() {
vector<int> arr;
int i;
while (scanf("%d", &i) != EOF) {
arr.push_back(i);
}
for (int i = 0;i < arr.size();i++) {
sum += arr[i];
}
diff = sum; // 初始差值等于sum

sort(arr.begin(), arr.end(), compare); // 优化1：提前排序

DFS(arr, 0, 0);

// sa + sb = sum
// sb – sa = diff
int sa = (sum – diff) / 2;
int sb = sa + diff;
printf("%d %d\\n", sb, sa);
return 0;
}