二分一个数组，使二者之差尽可能小

def get_less_pos(a, item_pos, current_pos): sum_a_set = sum(a[0:current_pos]) sum_b_set = sum(a[current_pos:]) diff = sum_b_set - sum_a_set result_pos = -2 item_value = a[item_pos] if item_pos < current_pos: if item_value < 0 and diff > -2 * item_value: result_pos = -1 diff += 2 * item_value temp_pos = current_pos for b_item in a[current_pos:]: if b_item > item_value and diff > 2 * (b_item - item_value): result_pos = temp_pos diff -= 2 * (b_item - item_value) temp_pos += 1 else: if item_value > 0 and diff > 2 * item_value: result_pos = -1 diff -= 2 * item_value temp_pos = 0 for a_item in a[0:current_pos]: if item_value > a_item and diff > 2 * (item_value - a_item): result_pos = temp_pos diff -= 2 * (item_value - a_item) return result_pos def exchange_item(a, current_pos): is_change = False for i in xrange(len(a)): pos = get_less_pos(a, i, current_pos) if pos == -1: is_change = True if i < current_pos: a[i], a[current_pos - 1] = a[current_pos - 1], a[i] current_pos -= 1 else: a[i], a[current_pos] = a[current_pos], a[i] current_pos += 1 elif pos != -2: is_change = True a[i], a[pos] = a[pos], a[i] return is_change, current_pos def main(a): sum_a = sum(a) temp_sum = 0 current_pos = 0 for item in a: if temp_sum + item < sum_a / 2: temp_sum += item current_pos += 1 else: break is_change = True while is_change: is_change, current_pos = exchange_item(a, current_pos) return current_pos if __name__ == "__main__": array = [4, 32, 452, 290, 19, 232, -25, 236, -992, 31] pos = main(array) print array, sum(array[0:pos]), sum(array[pos:]) print pos