2

Given real numbers $a_1,...,a_n \geq 0$, partition them into groups, so that the total product of each group's sum is maximal: $$M = (a_{i_{1,1}} + ... + a_{i_{k_1,1}}) \cdot ... \cdot (a_{i_{1,l}} + ... + a_{i_{k_l,l}}$$ You may put the numbers in any order, but each number has to come up exactly once.

Example: Given $0,1,1,2,2,3,4$, we can find their maximum to be $108 =(0+1+2)\cdot(1+2)\cdot(3)\cdot(4)$.

I was already able to prove that if each number is $\geq 2$, we just multiply up all numbers (so each group just gets a single number), and if the total sum of all numbers is $\leq 4$, we sum all numbers up (so put all numbers in a single group). I also know that $M \leq e^\frac{S}{e}$, where $S$ denotes the total sum of all numbers, and this upper bound is exactly matched if all group sums are equal to $e$.

A good strategy seems to be to get each groups sum as close as possible to $e$ or even more precisely, if $s$ denotes the sum of a group, get $\frac{s}{e^\frac{s}{e}}$ as close as possible to $1$, but I just can't seem to find a method that works general and that isn't super inefficient like just trying out all possible combinations. Maybe someone knows a method?

Orbit
  • 51
  • Could you please provide an example where the getting closest to e strategy isn't optimal? It seems to work for all the cases I've tried and the cases you mention – TheJack Aug 15 '23 at 12:39
  • Or are you just looking for an algorithm that best approximates e in each group? – TheJack Aug 15 '23 at 12:40
  • Take 1, 1, e/2, e/2 for example, then is it better to get the exact match for one group and have (1+1)(e/2+e/2), or is it better even it out and have (e/2+1)(e/2+1)? For small numbers you can just try out all combinations, but now take an array of hundreds of different small numbers numbers, then it's not so simple anymore and each number could go anywhere. Yes I'm looking for an algorithm to get the maximum possible value. Approximating each group to e was just a suggestion, but that alone doesn't give you a complete algorithm yet that works generally in all cases – Orbit Aug 15 '23 at 12:55
  • @Henriksupportsthecommunity well 1+e is closer to e then the 1 and e case since e-1>1...but yeah I understand this strategy doesn't seem to work in every case – TheJack Aug 15 '23 at 12:58
  • (I deleted my first comment because it was only partially written, when something happened that caused it to be send) How do you measure (and compare) closeness to $e$ for multiple sets? For the set ${1, e}$, your own conclusion shows that the maximum is $1+e$ by putting all the numbers in one group, whose sum is $1+e$. The other option has one group with a sum closer to $e$ (the sum is $e$) and one group with a sum ($1$) further from $e$ than the optimal solution. – Henrik supports the community Aug 15 '23 at 13:05
  • You take term $\frac{s}{e^\frac{s}{e}}$ and try to get it as close as possible to $1$ for each group, which measures the closeness to $e$ (plugging in $s=e$ gives you exactly 1, and in all other cases some value below 1). We then multiply all of these terms together and try to get the result as close as possible to $1$. This result is actually just the ratio of the product of sums to the upper bound $e^\frac{S}{e}$. To see how getting as close as possible to $e$ is important, try to find the maximum if the array consists of 108 $0.1$s. You get a maximum of $(0.1+...+0.1)^4 = 2.7^4$. – Orbit Aug 15 '23 at 13:15
  • @Henriksupportsthecommunity As Orbit said. This comes from the real values case. When you can choose any real value to cut up a line of length n into many parts and multiply the sizes of each then sizes of e are optimal because (x)^(1/x) has a maximum at e. The question is asking for an algorithm to generalize this for discrete variables without brute forcing every arrangement – TheJack Aug 15 '23 at 13:20
  • Using only the fact that no two numbers that are $\ge 2$ are in the same group, and letting $z$ be an upper bound on the number of groups (e.g. obtained by noting that no group has sum $<1$), we already get a runtime of $\mathcal O(z^s)$ where $s$ is the amount of numbers smaller than 2. – Sudix Aug 21 '23 at 15:46

1 Answers1

1

An exact solution is NP Hard.

Let’s restrict to the case where the sum of all numbers in the set is $2e$. Then, you need to need to partition the set into two subsets whose sum is as close as possible to each other. This is known as the partition problem (https://en.m.wikipedia.org/wiki/Partition_problem) and is NP-hard.

You can do reasonably well with approximation algorithms like Greedy.

Eric
  • 6,348