解题思路

题解区都是动态规划的思路，但其实位运算思路也挺好的！！！

（当然，你也可以用DP）

法一：位运算

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5E5 + 10; // 一定要5E5+10,不然就太小了 
int n, w, sum;
bitset<MAXN> bits(1); // 使用bitset即可 

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> w;
		sum += w;
		bits = bits | (bits << w); //相加，然后位运算 
	}
	for (int i = (sum >> 1); i >= 0; i--)
	{
		if (bits[i])
		{
			cout << i << " " << sum - i; // 输出后记得直接 return 0; 
			return 0;
		}
	}
	return 0;
}

法二：动态规划

#include <bits/stdc++.h>
using namespace std;

int n, a[500005], f[500005], sum; 

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i]; //总体重 
	}
	for (int i = 0; i < n; i++)
	{
		int j = sum; 
		while (j)
		{
			if (j - a[i] >= 0) f[j] = max(f[j], f[j - a[i]] + a[i]); //比较 
			j--;
		}
	}
	//注意如果这两个数不相等,则请把小的放在前面输出 
	if (f[sum / 2] < sum - f[sum / 2]) cout << f[sum / 2] << " " << sum - f[sum / 2] << endl;
	else cout << sum - f[sum / 2] << " " << f[sum / 2] << endl;
	return 0;
}

//O(n*(a[0]+a[1]+...+a[i-1])
#include<bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int f[500005];
int sum = 0;
//int max(int x, int y)//max
//{
//	if(x>y)
//	{
//		return x;
//	}
//	else
//	{
//		return y;
//	}
//}
int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
	{
		cin >> a[i];
		sum += a[i];//总体重 
	}
	for(int i = 0; i < n; i++)
	{
		int j = sum; 
		while(j)
		{
			if(j - a[i] >= 0)
			{
				f[j] = max(f[j],f[j-a[i]]+a[i]);//比较 
			}
			j--;
		}
	}
	//注意如果这两个数不相等,则请把小的放在前面输出 
	if(f[sum/2] < sum-f[sum/2])
	{
		cout << f[sum/2] << " ";
		cout << sum-f[sum/2] << endl;
	}
	else
	{
		cout << sum-f[sum/2] << " ";
		cout << f[sum/2] << endl;
	}
	return 0;
}

数组要开大点

//O(n*(a[0]+a[1]+...+a[i-1])
#include<bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int f[500005];
int sum = 0;
//int max(int x, int y)//max
//{
//	if(x>y)
//	{
//		return x;
//	}
//	else
//	{
//		return y;
//	}
//}
int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
	{
		cin >> a[i];
		sum += a[i];//总体重 
	}
	for(int i = 0; i < n; i++)
	{
		int j = sum; 
		while(j)
		{
			if(j - a[i] >= 0)
			{
				f[j] = max(f[j],f[j-a[i]]+a[i]);//比较 
			}
			j--;
		}
	}
	//注意如果这两个数不相等,则请把小的放在前面输出 
	if(f[sum/2] < sum-f[sum/2])
	{
		cout << f[sum/2] << " ";
		cout << sum-f[sum/2] << endl;
	}
	else
	{
		cout << sum-f[sum/2] << " ";
		cout << f[sum/2] << endl;
	}
	return 0;
}

hack 猴哥算法的测试用例：

样例 #1

2 2 2 3 3

样例 #2

1 2 3 4 5