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)]