python - 如何最大化加减组合？

Question

假设我有一个包含 10 个元素的列表 [a, b, c, d, e, f, g, h, i, j]，我可以将每个元素乘以 0, 1, 2, -1, -2 .

我使用的乘法因子的总和必须等于零。也就是说，如果我将五个数字乘以 -1，我必须将其他五个数字乘以 1，或者我可以将 a 乘以 2，b 和 c 乘以 -1，其余乘以 0。

我想找到此操作产生的总和最大的列表。

我怎样才能用Python编写这个代码？

我尝试对 [2, 1, 0, -1, -2] 的每次迭代进行编码，并删除不添加到 0 的列表，然后乘以原始列表，但是我陷入了困境。

Answer 1

您可以对列表进行排序，从两端向中心扫描，将 2 分配给较大的元素，将 -2 分配给较小的元素。

def baby_knapsack(xs):
    xs = sorted(xs, reverse=True)
    res =  list()
    n = len(xs)
    for i in range(n//2):
        res.extend(((xs[i], 2), (xs[-1-i], -2)))
    if n % 2 == 1:
        res.append((xs[n//2], 0))
    return res

xs = [-10, -5, 0, 5, 10, 15]

# In [73]: q.baby_knapsack(q.xs)                                           
# Out[73]: [(15, 2), (-10, -2), (10, 2), (-5, -2), (5, 2), (0, -2)]