提供一个想法,我暂时还没想到反例:
假设我们有N个bag来装这2N个数,首先将N个bag全部初始化为0, 用一个max变量实时
记录这N个bag的最大的那个, 将2N个数字从大到小排列,然后按照如下规则将这个2N个
数一个一个装袋:
case 1: 从最大的bag开始search,找到第一个这样的bag:满足这个bag的和加上这个
数不大于现在的max,如果能找到这个bag,就把这个数装到这个bag里面。
case 2: 找不到这样的bag,这说明已经search到最后那个最小的bag了(并且这个也不
满足case1的条件),如果这样的话,就将现在这个数加入这个bag,并且更新max为这个
bag的值。
example: 25 13 12 7 7 7
bags: 0 0 0, max = 0.
25: 25 0 0, max = 25. (case 2)
13: 25 13 0, max = 25. (case 1)
12: 25 (13,12) 0, max = 25. (case 1)
7: 25 (13,12) 7, max = 25. (case 1)
7: 25 (13,12) (7,7), max = 25 (case 1)
7: 25 (13,12) (7,7,7)max = 25 (case 1)