题目描述

链接：https://ac.nowcoder.com/acm/problem/17871
来源：牛客网

CSL手上有n个苹果，第i个苹果的质量是wi，现在他想把这些苹果分给他的好朋友wavator和tokitsukaze。但是CSL为了不让他们打架，根据质量决定尽量地均分成两堆分给他们。现在CSL想知道到底给每个人分多少质量的苹果。

注意：苹果不能劈开来，并且如果不能正好均分，tokitsukaze小姐姐会拿到重的那一堆。

题目思路

问题可以进行转化：wavator最多可以拿占总质量1/2的苹果，问最多能拿多重的。
因此可以套用01背包的解决方法。设dp[j]，表示容量为j时最多可装的苹果重量。
状态转移方程为 。（这里的价值就是苹果的质量）
注意，这里我们省略了对苹果序号的控制，所以转变成了一维数组。

在填充dp数组时，要从大序号向小序号遍历。由状态转移方程可以看出，每次填充都需要数组更靠前位置的值，且该位置应该是未对第i个苹果进行判断过的。如果从前向后遍历，就会造成后面的值被前面已经判断过w[i]的值影响。

for(int i=1;i<=n;i++)//i控制当前对第几个苹果进行判断
    {
        for(int j=sum/2;j>0;j--)//j控制当前遍历到的背包容量的大小，从大序号向小序号
        {
            if(j>=w[i])
            {
                dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
            }
        }
    }

完整代码

#include<bits/stdc++.h>
using namespace std;
int dp[105];
int sum = 0;

int main()
{
    int n;
    int w[105];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        sum+=w[i];
    }
    sort(w+1,w+n+1);
    dp[0] = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=sum/2;j>0;j--)
        {
            if(j>=w[i])
            {
                dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
            }
        }
    }
    printf("%d %d",dp[sum/2],sum-dp[sum/2]);
    return 0;
} 

总结

1、题目的重点在于转化。需要注意的是，不能直接通过如下方式（哪边小就给哪边添）直接构造两人苹果重量和。

for(int i=2;i<=n;i++)
    {
        if(sum2<sum1)
        {
            sum2+=w[i];
        }
        else
        {
            sum1+=w[i];
        }
    }

2、刚刚又复习了录播课！发现内层循环从小序号向大序号循环时构造的是完全背包！