技巧    
    可行性01背包
思路
    尽量平均分  那么最好的可能就是一人一半 ，如果奇数个数的话就是拆成n和n+1。
    那将问题转换成这一对苹果能否装满容量为 sum / 2重量的背包。 如果不能，做多能塞满多少。
    所以就是很明显的可行性01背包问题
实现 
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

func NC17871(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var n int
	Fscan(in, &n)
	a := make([]int, n+1)
	sum := 0
	for i := 1; i <= n; i++ {
		Fscan(in, &a[i])
		sum += a[i]
	}
	avg := sum / 2
	dp := [105][5005]bool{}
	dp[0][0] = true

	for i := 1; i <= n; i++ {
		for j := avg; j >= 0; j-- {
			dp[i][j] = dp[i-1][j]
			if !dp[i][j] && j-a[i] >= 0 {
				dp[i][j] = dp[i][j] || dp[i-1][j-a[i]]
			}
		}
	}

	for i := avg; i >= 0; i-- {
		if dp[n][i] {
			Fprintln(out, i, sum-i)
		}
	}

}
func main() {
	NC17871(os.Stdin, os.Stdout)
}