algorithm - 将列表分成两部分，它们的总和彼此最接近

Question

这是一个硬算法问题:

将列表分成两部分(总和)，它们的总和最接近(最)彼此

列表长度为 1 <= n <= 100，问题中给出的(数字)权重为 1<=w<=250。

例如:23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

我有一个算法，但它不适用于所有输入。

1. 初始化。列表 list1 = [], list2 = []
2. 排序元素(给定列表)[23 32 34 65 95 123 134]
3. 弹出最后一个(最多一个)
4. 插入差异较小的列表

实现: 列表 1 = [], 列表 2 = []

1. 选择 134 插入列表 1。列表 1 = [134]
2. 选择 123 插入列表 2。因为如果你插入 list1 差异会变大
   3. 选择 95 并插入 list2 。因为 sum(list2) + 95 - sum(list1) 更少。

等等……

Answer 1

您可以将其重新表述为 knapsack problem .

您有一个总重量为 M 的元素 list ，这些元素应该装入最大重量为 M/2 的箱子中。装在垃圾箱中的元素的重量应尽可能重，但不要超过垃圾箱的容量。

对于所有权重都是非负的情况，这个问题只有weakly NP-complete并具有多项式时间解。

可以在 Wikipedia 上找到有关此问题的动态规划解决方案的描述。 .