xanaxxx's blog

Minimum sum of product of 2 arrays
By xanaxxx, history, 9 months ago, In English

So there is this known problem: you have 2 arrays (let's say a and b) both of size n and you have to arrange them in such a way that the value $$$\sum_{i=1}^{n}a_{i}b_{i}$$$ is as small as possible. Intuitively, an idea is to pair the biggest element in a with the smallest in b, the second largest in a with the second smallest in b and so on. But I would like to see some sort of proof because this only relies on intuition. Thanks in advance.

Example: initially a = {3, 1, 1}, b = {6, 5, 4}. After performing the algorithm a = {3, 1, 1}, b = {4, 5, 6}. Answer is 3*4 + 1*5 + 1*6 = 23

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can just prove it in this way like If u try to swap any 2 pairs of the correct combination (bigger a with smaller b's) you would get the final sum bigger than the previous.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rearrangement Inequality

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Wow, thanks for this, I will definitely save this somewhere

    → Reply