题解 | #CSL分苹果#

01 背包模板。

设 $d{p}_{i,j}dp\_\{i,j\}$ 表示前 $ii$ 个物品是否能组成重量 $jj$：

$d{p}_{i,j}\leftarrow d{p}_{i-1,j}\text{\&nbs***bsp;}d{p}_{i-1,j-a_i}dp\_\{i,j\}\backslash leftarrow\; dp\_\{i-1,j\}~\backslash text\{OR\}~dp\_\{i-1,j-a\_i\}$

然后从 ${\displaystyle \frac{sum}{2}}\backslash dfrac\{sum\}\{2\}$ 处开始找到的第一个最优答案就好了。

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e2 + 5, M = (int) 1e4 + 5;
bool dp[M];
int main(){
    int n = init(), sum = 0;
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        int x = init(); sum += x;
        for (int j = M - 5; j >= x; --j)
            dp[j] |= dp[j - x];
    }
    int ans = sum;
    for (int x = sum - 1; x >= (sum + 1) / 2; --x)
        if (dp[x]) ans = x;
    print(sum - ans), putchar(' '), print(ans), putchar('\n');
}