C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2023-05-14 21:41:06

#include<bits/stdc++.h>
using namespace std;
int n,a[110],dp[10010],sum=0;
int main(){
        cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	for(int i=1;i<=n;i++) for(int j=sum/2;j>=a[i];j--)  dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
	cout<<dp[sum/2]<<" "<<sum-dp[sum/2];
}

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 616K, 提交时间: 2020-03-23 13:29:35

#include<bits/stdc++.h>
using namespace std;
int f[10005];
int main()
{
    int n,s=0,w;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>w;
        s+=w;
        for(int j=10000;j>=w;j--)
            f[j]=max(f[j],f[j-w]+w);
    }
    cout<<f[s/2]<<' '<<s-f[s/2];
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 592K, 提交时间: 2020-02-27 23:17:29

#include<bits/stdc++.h>
using namespace std;
int n,sum;
bitset<10005> f;
int main()
{
	cin>>n;
	f[0]=1;
	for(int i=1,w;i<=n;++i)
	{
		cin>>w;
		sum+=w;
		f|=f<<w;
	}
	for(int i=sum+1>>1;;++i)
	if(f[i]==1)
	{
		cout<<sum-i<<" "<<i<<endl;
		break;
	}
	return 0;
}

Python3 解法, 执行用时: 264ms, 内存消耗: 4740K, 提交时间: 2022-10-26 20:50:42

n=int(input())
a=list(map(int,input().split()))
dp=[0]*(sum(a)+1)
for i in range(n):
	for j in range(sum(a),a[i]-1,-1):
		dp[j]=max(dp[j],dp[j-a[i]]+a[i])
print(dp[sum(a)//2],sum(a)-dp[sum(a)//2])