Question

求一道动态规划题的解答思路以及状态方程

有N个数，将它们分为两组，两组中数的数量尽量平分，求着两组数和的差的最小值。
1 2 2 3 min=4-4=0

Answer 1

把n个数从大到小排列起来：
x1>=x2>=x3>=……>=xn.
如果x1-(x2+x3)>=0,那么x1-(x2+x3+x4)?;
如果x1-(x2+x3)<0,那么(x1+x4)-(x2+x3)?.
如果x1-(x2+x3)>=0,x1-(x2+x3+x4)>=0,那么x1-(x2+x3+x4+x5)?;
如果x1-(x2+x3)>=0,x1-(x2+x3+x4)<0,那么(x1+x5)-(x2+x3+x4)?
依此类推，如果差不小于0，那么下一个数加到减数中；如果差小于0，那么下一个数加到被减数中。并相应改变判别式，直至第n个数。