How do I pick elements from two arrays such that their sum is minimum?

Question

I have two arrays of equal length filled with integers(could be positive or negative but never 0). At each index I can either choose the element of array1 or from array2, and the absoulute value of the sum of such elements should be minimum.

Eg:

a1 = [2, 2, 1]
a2 = [-3, -3, -4]

The correct answer would be to choose like this:

At index 0 : -3 from a2
At index 1 : 2 from a1
At index 2 : 1 from a1

Thus, the final sum would be 0.

Answer 1

First, simplify the question:

• Create array b, where b[i] = a1[i] - a2[i].
• sumA1 = sum of each elements in a1.

Then the problem becomes:

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.

Then this question is similar to this one: Given an input array find all subarrays with given sum K

Or, refer to this article:

• Subarray whose sum is closest to K
• Find subarray with given sum | Set 2 (Handles Negative Numbers)

And, to go back to OP's question:

• Any indices picked in b are for a2.
• Any indices not picked in b are for a1.

Answer 2

Here is a dynamic programming solution that finds the minimum value for pos + abs(neg + pos)(as per OP's update) and prints one candidate solution. We need to save both total sum and sum of positive integers as dp state to find the minimum. I am not sure if we can solve it without the pos dimension. Time complexity is O(#elements * (sum of absolute values of elements)^2). Of course if the individual numbers are very large this is not a feasible solution. In that case the brute force approach will work when number of elements is ~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]

Answer 3

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

this code suggest pick a1[0] + a1[1] + a2[2] = 2 + 2 + (-4), different from OP's pick, but is also correct.

Update per OP's follow up question in comment to this answer:

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)

With the new objective function, there are still multiple solutions. It can be (-3, 2, 1) or (2, -3, 1)