题解 | 数组划分

题目链接

题目:把含若干数字的数组任意划分成两个子数组，使得两个子数组的和相差最小。

本题采用3种解法，最后一种ac。

解法一：动态规划（数组和不大时可以采用，否则容易超时）

思路：设数组总和为sum，目标是找到一个子数组使得子数组和尽可能<=sum/2，这样两个数组和若相等，则和相差最小是0。

对于每一个数组中数字，都要更新dp数组：如果之前能凑出vec[i](数组元素），那么现在有了j，你就能凑出vev[i]+j了（前提是 vev[i]+j 不超过 target）

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int sum = 0;
int min_partition(vector<int> vec) {
	int target = sum / 2;//
	//dp[i]=true表示：和为i的数组能凑出
	vector<bool> dp(target + 1, false);
	dp[0] = true;
	//动态规划填表
	for (int i = 0; i<vec.size(); i++) {
		for (int j = target; j-vec[i] >=0; j--) {//逆着判断可以避免重复
			if (dp[j - vec[i]]) {
				dp[j] = true;
			}
		}
	}

	for (int i = target; i >= 0; i--) {
		if (dp[i]) {
			return i;//返回最接近target的和
			break;
		}
	}
	return -1;
}
int main(){
	vector<int> vec;
	int data;
	while (scanf("%d", &data)!=EOF) {
		vec.push_back(data);
		sum += data;
	}
	int a_sum = min_partition(vec);
	int b_sum = sum - a_sum;
	//降序输出两个元素和
	printf("%d %d", max(a_sum, b_sum),min(a_sum, b_sum));
	return 0;
}

解法二：贪心算法：先排序，依次把最大的数字插入和最小的数组中，快速得出近似出最优解!

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;
int sum = 0;
void min_partition(vector<int> &vec,int &a_sum,int &b_sum) {
	sort(vec.begin(), vec.end());
	int sub_sum = 0;
	for (int i = vec.size()-1; i>=0; i--) {//从大的数字开始，使得子数组和尽快接近总和的一半
		if (a_sum >= b_sum) {
			b_sum += vec[i];
		}
		else {
			a_sum += vec[i];
		}
	}
}
int main(){
	vector<int> vec;
	int data;
	while (scanf("%d", &data)!=EOF) {
		vec.push_back(data);
		sum += data;
	}
	int a_sum=0,b_sum= 0;
	min_partition(vec, a_sum, b_sum);
	//降序输出两个元素和
	printf("%d %d", max(a_sum, b_sum),min(a_sum, b_sum));
	return 0;
}

解法三：DSP+剪枝

思路：只要sa+vec[i]不超过数组总和的一半，就递归增加sa（保存子数组和）的值。

为了提高程序运行效率，先把数组降序排，预测更新全局最优的diff值，并且判断剪枝：如果预判发现 diff 已经是 0 或 1（理论极限），或者当前数字大到不可能产生更优解（2*vec[pos] > sum），就立刻设置 flag=true，停止一切后续搜索。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int sum = 0;
int diff = 0;//差值
bool flag = false;//是否剪枝
void dfs(vector<int>& vec, int pos, int sa) {
	if (pos == vec.size()||flag)return;//遍历完数组or需要剪枝
	int newdiff;
	 newdiff=abs(2 * (sa + vec[pos]) - sum);
	if (newdiff < diff) {//更新最小差值
		diff = newdiff;
		if (diff == 0 || diff == 1 || 2*vec[pos] > sum) {
			flag = true;//剪枝优化
		}
	}
   //1.vec[pos]可放入sa时
	if ((sa + vec[pos])*2 < sum) {//sa+ vec[pos]小于sum/2
		dfs(vec, pos + 1, sa + vec[pos]);//往sa继续加数据
	}
	//2.vec[pos]不放入sa时
	dfs(vec, pos + 1, sa);
}
bool compare(int l, int  r) {
	return l > r;
}
int main(){
	vector<int> vec;
	int i;
	while (scanf("%d", &i) != EOF) {
		vec.push_back(i);
		sum += i;
	}
	diff = sum;//初始化差值上限
	sort(vec.begin(), vec.end(),compare);//降序排
	dfs(vec, 0, 0);
	int sa = (sum - diff) / 2;//diff=(sum-sa)-sa=sum-2*sa
	printf("%d %d\n", sa + diff, sa);//降序输出
    return 0;
}