[讨论]分土豆问题

elimqiu

任给土豆一堆，欲将其尽可能（按重量）平分成两堆，求步骤。
数学地说就是随机地给定n个正数 A1,...,An, 求得出{1,...,n}的子集{m1,...,mk}的算法使：
|(Am1+...+Amk) - ((A1+..+An)-(Am1+...Amk))| = |2(Am1+...+Amk)-(A1+...+An)|
= min { |2(As1+...+Asp)-(A1+...+An)| ： E = {s1,...,sp} 含于 {1,...,n}, |E| = p, 1≤p≤n}
这个问题的难点在于能否找到只需多项式时间的算法而不是需时更多的算法。

musicbug88

有意思的问题，关注一下

elimqiu

谢谢关注。搞算法的人到底跟没进过学堂的翻身农奴有多大区别就看这题了：-）

wangyangkee

elimqiu不是笨蛋，不愚蠢，不驴打滚，不狗屎堆逻辑，elimqiu不是白痴，elimqiu不是饭桶，不是网痞，不是下三滥，