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?
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.