/*
要求把a数组分成两个集合，两个集合人数最多差1，并且元素之和的差尽可能小
那只要把所有可行的列出来即可
01二维背包，即体积是个二维数据，那么我们的背包状态也应该设为二维
dp[j][k]设为 有j个人，体积为k的状态是否可行
第一维上限是人数的一般，第二维上限是元素总和的一半
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,a[
200];
bool dp[
105][
505*
100];
int main(){
while(cin>>
n){
int sum=
0;
for(
int i=
1;i<=n;i++)cin>>a[i],sum+=
a[i];
memset(dp,0,
sizeof dp);
int W1=(n+
1)/
2,W2=sum/
2;dp[
0][
0]=
1;
for(
int i=
1;i<=n;i++
)
for(
int j=W1;j>=
1;j--
)
for(
int k=W2;k>=a[i];k--
)
dp[j][k]|=dp[j-
1][k-
a[i]];
int ans=
0;
for(
int k=
1;k<=W2;k++
)
if(dp[W1][k])ans=
max(ans,k);
if(n%
2)
for(
int k=
1;k<=W2;k++
)
if(dp[W1-
1][k])ans=
max(ans,k);
cout<<ans<<
" "<<sum-ans<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11179716.html
