求一道动态规划题的解答思路以及状态方程
问题描述:
求一道动态规划题的解答思路以及状态方程
有N个数,将它们分为两组,两组中数的数量尽量平分,求着两组数和的差的最小值.
1 2 2 3 min=4-4=0
答
把n个数从大到小排列起来:
x1>=x2>=x3>=……>=xn.
如果x1-(x2+x3)>=0,那么x1-(x2+x3+x4)?;
如果x1-(x2+x3)=0,x1-(x2+x3+x4)>=0,那么x1-(x2+x3+x4+x5)?;
如果x1-(x2+x3)>=0,x1-(x2+x3+x4)