Codevs 1959 拔河比赛

http://codevs.cn/problem/1959/

这里写图片描述
有两种做法：

第一种：dp；不过这个dp比较难想，而且比较特别，，解释见代码注释。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath> 
using namespace std;
int n,sum,k,a[105];
bool f[105][45005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    k=(n+1)/2;
    int sum1=(sum+1)/2;

    f[0][0]==f[1][0]=1;

    for(int i=1;i<=n;i++)
     for(int j=sum1;j>=a[i];j--)
      for(int q=k;q>=1;q--)
       f[q][j]=f[q][j]||f[q-1][j-a[i]];//f[i][j]表示选i个人能否达到j这个重量

    int ans;
    for(int i=sum1;i>0;i--)
     if(f[k][i]) {ans=i;break;} 
    printf("%d %d",min(ans,sum-ans),max(ans,sum-ans));
    return 0;     
}

第二种：随机+贪心
我们把w数组各元素的位置随机交换一下，取前面的n/2个为其中一组，不断更新答案。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath> 
#include<ctime>
using namespace std;
int n,a[109],sum,ans,delta=45009;
int main()
{
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    for(int i=1;i<=200000;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x=rand()%n+1;
            int y=rand()%n+1;
            swap(a[x],a[y]);
        }
        int s1=0;
        for(int j=1;j<=n/2;j++) s1+=a[j];

        int s2=sum-s1;
        if(abs(s1-s2)<delta) ans=min(s1,s2),delta=abs(s1-s2);
    }
    printf("%d %d",ans,sum-ans);
    return 0;
}