假设我有一个包含 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 的列表,然后乘以原始列表,但是我陷入了困境。
最佳答案
您可以对列表进行排序,从两端向中心扫描,将 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)]
关于python - 如何最大化加减组合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57453491/