链接：https://ac.nowcoder.com/acm/problem/17871

题目描述

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

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

输入描述:

第一行输入一个整数n(2 ≤ n ≤ 100)，第二行n个整数，表示每个苹果的质量wi(1 ≤ wi ≤ 100)。

标输出描述:

输出两个整数，分别表示wavator和tokitsukaze得到的苹果的质量。
示例1
输入
3
2 2 2
输出
2 4

思路

给wavator一个总容量为苹果总重量一半的容器，求出在这个容器中最多可以装下多少重量的苹果，即为wavator最多可以得到的苹果重量，剩下的即为tokitsukaze的苹果重量。

#include<iostream>
#include<cmath>
using namespace std;
int dp[5005],w[105];//因为n<100&&wi<=100,所以sum<=10000,那么dp数组大小要开sum/2这么大 
int main(){
    int n,sum=0,ma;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];//每个苹果的价值 
        sum+=w[i];
    }
    ma=sum/2;//wavator的容器容量为sum/2 
    for(int i=1;i<=n;i++){
        for(int j=ma;j>=w[i];--j){
            dp[j]=max(dp[j],dp[j-w[i]]+w[i]);//j大小的容量可以装下最多多少价值的东西 
        }
    }//让ma容量的容器装得的苹果重量最大 

    cout<<dp[ma]<<" "<<sum-dp[ma]; 
    return 0;
}