牛客小白月赛7 G.CSL分苹果

题目链接

题目描述

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

简单背包，重量即价值，背包最大容量就是总容量的一半，AC代码如下：

#include<bits/stdc++.h> typedef long long ll; using namespace std; int n,sum=0,w[105],dp[10005]; int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&w[i]),sum+=w[i]; for(int i=0;i<n;i++){ for(int j=sum/2;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+w[i]); } } printf("%d %d",min(dp[sum/2],sum-dp[sum/2]),max(dp[sum/2],sum-dp[sum/2])); }