如何从两个数组中选择元素,使它们的总和最小?
How do I pick elements from two arrays such that their sum is minimum?
我有两个等长的数组,里面填满了整数(可以是正数也可以是负数,但绝不能为 0)。在每个索引处,我可以选择array1或array2中的元素,并且这些元素之和的绝对值应该是最小的。
例如:
a1 = [2, 2, 1]
a2 = [-3, -3, -4]
正确答案应该是这样选择:
At index 0 : -3 from a2
At index 1 : 2 from a1
At index 2 : 1 from a1
因此,最终总和为 0。
首先,简化问题:
- 创建数组
b
,其中 b[i] = a1[i] - a2[i]
。
sumA1
= a1
. 中每个元素的总和
那么问题就变成了:
Find a sub array from b
, mark as c
, mark its sum as sumC
which should be closest to sumA1
.
Or, you can also say it should have minimal Math.abs(sumC - sumA1)
.
BTW, if c
is empty, it's also valid, which means choose all indices from a1
.
那么这道题和这道题类似:Given an input array find all subarrays with given sum K
或者,参考这篇文章:
然后,回到 OP 的问题:
- 在
b
中选择的任何索引都用于 a2
。
b
中未选择的所有索引均用于 a1
。
import itertools as iter
a = [a1, a2]
p = len(a1)
idx_to_pick = min(iter.product(*([[0, 1]]*p)),
key=lambda b: abs(sum([a[i][j] for i, j in zip(b, range(p))])))
此代码建议选择 a1[0] + a1[1] + a2[2] = 2 + 2 + (-4)
,与 OP 的选择不同,但也是正确的。
更新 每个 OP 对该答案的评论中的后续问题:
import itertools as iter
a1 = [2, 2, 1]
a2 = [-3, -3, -4]
a = [a1, a2]
p = len(a1)
def obj_func(b):
arr = [a[i][j] for i, j in zip(b, range(p))]
return sum([x for x in arr if x > 0]) + abs(sum(arr))
idx_to_pick = min(iter.product(*([[0, 1]]*p)), key=obj_func)
有了新的objective功能,仍然有多种解决方案。它可以是 (-3, 2, 1) 或 (2, -3, 1)
这是一个动态规划解决方案,它找到 pos + abs(neg + pos)
的最小值(根据 OP 的更新)并打印一个候选解决方案。我们需要将总和和正整数之和都保存为 dp 状态以找到最小值。我不确定我们是否可以在没有 pos
维度的情况下解决它。时间复杂度为 O(#elements * (sum of absolute values of elements)^2)
。当然,如果个体数非常大,这不是一个可行的解决方案。在这种情况下,当元素数量为 ~20
.
时,蛮力方法将起作用
a1 = [2, 1, 1, -1]
a2 = [-1, -2, -2, -4]
memo = {} # to store dp state
nxt = {} # for reconstructing path
def foo(a1, a2, index, total, pos):
if index == len(a1):
return pos + abs(total)
if (index, total, pos) in memo:
return memo[(index, total, pos)]
# take from first array
if a1[index] > 0:
r1 = foo(a1, a2, index+1, total + a1[index], pos+a1[index])
else:
r1 = foo(a1, a2, index+1, total + a1[index], pos)
# take from second array
if a2[index] > 0:
r2 = foo(a1, a2, index+1, total + a2[index], pos+a2[index])
else:
r2 = foo(a1, a2, index+1, total + a2[index], pos)
# save path taken at this step
if r1 < r2:
nxt[index] = 0
else:
nxt[index] = 1
memo[index, total, pos] = min(r1, r2)
return min(r1, r2)
print('minimum sum:', foo(a1, a2, 0, 0, 0)) # minimum sum: 2
# path reconstruction
path = []
node = 0
while node < len(a1):
path.append(nxt[node])
node += 1
print('path:', path) # path: [1, 0, 0, 0]
我有两个等长的数组,里面填满了整数(可以是正数也可以是负数,但绝不能为 0)。在每个索引处,我可以选择array1或array2中的元素,并且这些元素之和的绝对值应该是最小的。
例如:
a1 = [2, 2, 1]
a2 = [-3, -3, -4]
正确答案应该是这样选择:
At index 0 : -3 from a2
At index 1 : 2 from a1
At index 2 : 1 from a1
因此,最终总和为 0。
首先,简化问题:
- 创建数组
b
,其中b[i] = a1[i] - a2[i]
。 sumA1
=a1
. 中每个元素的总和
那么问题就变成了:
Find a sub array from
b
, mark asc
, mark its sum assumC
which should be closest tosumA1
.Or, you can also say it should have minimal
Math.abs(sumC - sumA1)
.BTW, if
c
is empty, it's also valid, which means choose all indices froma1
.
那么这道题和这道题类似:Given an input array find all subarrays with given sum K
或者,参考这篇文章:
然后,回到 OP 的问题:
- 在
b
中选择的任何索引都用于a2
。 b
中未选择的所有索引均用于a1
。
import itertools as iter
a = [a1, a2]
p = len(a1)
idx_to_pick = min(iter.product(*([[0, 1]]*p)),
key=lambda b: abs(sum([a[i][j] for i, j in zip(b, range(p))])))
此代码建议选择 a1[0] + a1[1] + a2[2] = 2 + 2 + (-4)
,与 OP 的选择不同,但也是正确的。
更新 每个 OP 对该答案的评论中的后续问题:
import itertools as iter
a1 = [2, 2, 1]
a2 = [-3, -3, -4]
a = [a1, a2]
p = len(a1)
def obj_func(b):
arr = [a[i][j] for i, j in zip(b, range(p))]
return sum([x for x in arr if x > 0]) + abs(sum(arr))
idx_to_pick = min(iter.product(*([[0, 1]]*p)), key=obj_func)
有了新的objective功能,仍然有多种解决方案。它可以是 (-3, 2, 1) 或 (2, -3, 1)
这是一个动态规划解决方案,它找到 pos + abs(neg + pos)
的最小值(根据 OP 的更新)并打印一个候选解决方案。我们需要将总和和正整数之和都保存为 dp 状态以找到最小值。我不确定我们是否可以在没有 pos
维度的情况下解决它。时间复杂度为 O(#elements * (sum of absolute values of elements)^2)
。当然,如果个体数非常大,这不是一个可行的解决方案。在这种情况下,当元素数量为 ~20
.
a1 = [2, 1, 1, -1]
a2 = [-1, -2, -2, -4]
memo = {} # to store dp state
nxt = {} # for reconstructing path
def foo(a1, a2, index, total, pos):
if index == len(a1):
return pos + abs(total)
if (index, total, pos) in memo:
return memo[(index, total, pos)]
# take from first array
if a1[index] > 0:
r1 = foo(a1, a2, index+1, total + a1[index], pos+a1[index])
else:
r1 = foo(a1, a2, index+1, total + a1[index], pos)
# take from second array
if a2[index] > 0:
r2 = foo(a1, a2, index+1, total + a2[index], pos+a2[index])
else:
r2 = foo(a1, a2, index+1, total + a2[index], pos)
# save path taken at this step
if r1 < r2:
nxt[index] = 0
else:
nxt[index] = 1
memo[index, total, pos] = min(r1, r2)
return min(r1, r2)
print('minimum sum:', foo(a1, a2, 0, 0, 0)) # minimum sum: 2
# path reconstruction
path = []
node = 0
while node < len(a1):
path.append(nxt[node])
node += 1
print('path:', path) # path: [1, 0, 0, 0]