题解 | #CSL分苹果#

• 题目考点：dp -- 01背包 （无脑dfs肯定T ，后面附上60分dfs吧）
• 题目大意：将a数组中的数分成两组，使得两组中的数的和尽量接近，输出两组数的和（若无法平均，优先输出较小的数）
• 题目分析：01背包问题，若a数组中的数总和为sum ，可以假想一个体积为sum / 2的背包，将其尽量装满即可
  代码如下：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 10010; // 100个苹果每个质量都是100的话，需要一个10000的背包
                     //所以dp数组至少需要5000, 这里奢侈了一把
int a[N], n, sum = 0;
int dp[N]; 

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), sum += a[i];
    int v = sum / 2;

    for(int i = 1; i <= n; i++)
    for(int j = v; j >= a[i]; j --)
        dp[j] = max(dp[j], dp[j - a[i]] + a[i]);

    printf("%d %d", dp[v], sum - dp[v]);

    return 0;
}

60分dfs给大家助助兴：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;
int a[N], sum = 0, n;
int ans = 0;
bool v[N];

void dfs(int w, int k)
{
    if(k > n){ans = max(ans, w); return ;}
    if(w + a[k] <= sum / 2)
        dfs(w + a[k], k + 1);
    dfs(w, k + 1);
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), sum += a[i];
    dfs(0, 1);
    printf("%d %d", ans, sum - ans);
    return 0;
}