python - Minimize sum of product of two uneven consecutive arrays

Question

I've got an optimization problem in which I need to minimize the sum product of two uneven but consecutive arrays, say:

A = [1, 2, 3]
B = [4, 9, 5, 3, 2, 10]

Shuffling of values is not allowed i.e. the index of the arrays must remain the same. In other words, it is a distribution minimization of array A over array B in consecutive order.

Or: Given that len(B)>=len(A) Minimize the sum product the values of Array A of length n over n values of array B without changing the order of array A or B.

In this case, the minimum would be:

min_sum = 1*4 + 2*3 + 3*2 = 16

A brute force approach to this problem would be:

from itertools import combinations

sums = [sum(a*b for a,b in zip(A,b)) for b in combinations(B,len(A))]
min_sum = min(sums)

I need to do this for many sets of arrays however. I see a lot of overlap with the knapsack problem and I have the feeling that it should be solved with dynamic programming. I am stuck however in how to write an efficient algorithm to perform this.

Any help would be greatly appreciated!

question from:https://stackoverflow.com/questions/65884107/minimize-sum-of-product-of-two-uneven-consecutive-arrays

Answer 1

Having two lists

A = [1, 2, 3]
B = [4, 9, 5, 3, 2, 10]

the optimal sum product can be found using:

min_sum = sum(a*b for a,b in zip(sorted(A), sorted(B)[:len(A)][::-1]))

In case A is always given sorted, this simplified version can be used:

min_sum = sum(a*b for a,b in zip(A, sorted(B)[:len(A)][::-1]))

The important part(s) to note:

• You need factors of A sorted. sorted(A) will do this job, without modifying the original A (in contrast to A.sort()). In case A is already given sorted, this step can be left out.
• You need the N lowest values from B, where N is the length of A. This can be done with sorted(B)[:len(A)]
• In order to evaluate the minimal sum of products, you need to multiply the highest number of A with the lowest of B, the second hightst of A with the second lowest of B. That is why after getting the N lowest values of B the order gets reversed with [::-1]

Output

print(min_sum)
# 16
print(A)
# [1, 2, 3]              <- The original list A is not modified
print(B)
# [4, 9, 5, 3, 2, 10]    <- The original list B is not modified