题解 | 第二题

#include<iostream>

#include<vector>
#include<string.h>// getline头文件
#include<math.h>

using namespace std;

int Stoi(char* begin)  // 如果不合法返回-1，合法返回0
{
	int sum = 0;
	while (begin != NULL && *begin != ' ' && *begin != '\0') {
		sum *= 10;
		if (*begin <= '9' && *begin >= '0') {
			sum += *begin - '0';
		}
		else {
			return -1;
		}
		begin++;
	}
	return sum;
}

int sum;// 数组总和
int half;// 数组总和的一半
int vector_length;// 数组的总长度
int String2Vector(string& buf, vector<int>& BufV) // 如果不合法返回-1，合法返回0
{
	char del = ' ';
	char* token = strtok((char*)buf.c_str(), &del);
	while (token != NULL) {
		int cur = Stoi(token);
		if (cur == -1) {
			return -1;
		}
		BufV.push_back(cur);
		token = strtok(NULL, &del);
	}
	sum = 0;
	for (auto i : BufV) {
		sum += i;
	}
	half = sum / 2;
	vector_length = BufV.size();
	return 0;
}

int best;// 记录分割之差最小所划分出来的子数组的和
bool fin_flag;// 如果找到分割之差最小的方法，递归可以提前结束
void dfs(vector<int>& BufV, int index, int value) {
	if (fin_flag || (index == vector_length)) {// 递归结束
		return;
	}
	if (value == half) { // 剪枝，如果已经达到分割之差最小
		best = half;
		fin_flag = true;
		return;
	}
	// 如果正好达到half则不再继续递归。已经使分割之差最小
	int cur = BufV[index];
	if (cur >= half) {
		best = cur;
		fin_flag = true;
		return;
	}
	// 如果有一个超出half的单个元素，则剪枝单独成组，不必再递归

	int remain = value + cur;// 如果保留当前元素，则本次递归下去的和就是value + cur
	int abandon = value;// 不保留当前元素则为value值
	if (abs(half - remain) < abs(half - best)) {
		best = remain;
	}
	else if (abs(half - abandon) < abs(half - best)){
		best = abandon;
	}
	dfs(BufV, index + 1, remain);
	dfs(BufV, index + 1, abandon);
	// 分成两条递归路径，一条保留一条舍弃
}

int main()
{
	string buf;
	while (getline(cin, buf)) {
		vector<int> BufV;
		int flag = String2Vector(buf, BufV);
		if (flag == -1) {
			cout << "ERROR" << endl;
		}
		else {
			fin_flag = false;
			dfs(BufV, 0, 0);
			int outputa = best;
			int outputb = sum - best;
			if (outputa < outputb)
				swap(outputa, outputb);
			cout << outputa << " " << outputb << endl;
		}
	}
	return 0;
}

两种做法：一种按照传统dp思路做，另一种是按照暴力搜索+剪枝

传统dp：既然要将数组分成两组，并且要求两组和之差最小，首先可以想到，两个数组越接近总和的一半，差就越小。

可以看作是背包问题，总和的一半视为背包容量上限。注意一个细节，sum/2可能取整损失精度，但没关系啊，我们凑比较小的一组子数组即可，使其尽可能接近sum/2。因为在sum为奇数的情况下，无论怎么划分，都会有一组和更小，所以求出和最接近sum的子数组即可满足条件，不会有更优化分割法。状态转移方程: dp[i][cap] = max{dp[i - 1][cap], dp[i - 1][cap - cur] + cur}

缺陷在于，sum/2可能非常大，像题目中给出的几组数据，元素个数并不多，而总和很大，导致用于制表的空间很大，超出题目内存限制。

暴力搜索+剪枝：一个元素只有保留与舍弃两种可能，对于数组中每一个元素，计算保留与舍弃两种结果，比较哪个与sum/2更接近即可，然后递归到next元素。这样有2^n中可能，会超时，所以需要剪枝。一旦和已经等于sum/2，便不需要递归了，已经求出最优解。如果有一个元素自身超过sum/2，那么把这个元素单独成组即为最优解，不必继续递归。