CSL分苹果 题解

将问题转化为wavator拿的苹果质量尽可能多，则变成一个容量为sum>>1的背包问题。
由于题目要求的是质量尽可能多，那么w[i]等价于v[i]
套用01背包模板，注意dp数组的大小至少要开到sum>>1

#include <bits/stdc++.h>
using namespace std;
int a[5050];
int dp[5050];//维护当前到第几个数，差值
int main()
{
    int sum=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    int m=sum>>1;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i];j--)
        {
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    }
    printf("%d %d\n",dp[m],sum-dp[m]);
}