动态规划，背包问题

题意：

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

注意：苹果不能劈开来，并且如果不能正好均分，tokitsukaze小姐姐会拿到重的那一堆。
输入描述:
第一行输入一个整数n(2 ≤ n ≤ 100)，第二行n个整数，表示每个苹果的质量wi(1 ≤ wi ≤ 100)。
输出描述:
输出两个整数，分别表示wavator和tokitsukaze得到的苹果的质量。

分析：

我们来看这题究竟要解决什么问题：
sum 为所有苹果的重量
我们需要在区间[1,n]中找到最大的不大于(sum>>1)的值
是否如此？
即sum>>1是一个是上界，我们应该在不超过上界的情况下尽可能地拿走苹果。
这其实就是背包问题了。

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 110;
const int max_v = 1e4 + 100;
int dp[max_n][max_v];
int in[max_n];

int main() {
    ios::sync_with_stdio(0);
    int n;cin >> n;int sum = 0;
    for (int i = 1;i <= n;i++) {
        cin >> in[i];
        sum += in[i];
    }for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= sum / 2;j++) {
            dp[i][j] = dp[i - 1][j];
            if (j < in[i])continue;
            dp[i][j] = max(dp[i][j], dp[i - 1][j - in[i]] + in[i]);
        }
    }cout << dp[n][sum / 2] << " " <<sum - dp[n][sum / 2] << endl;
}