2
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – TheJack
    Aug 15, 2023 at 12:39
  • $\begingroup$ Or are you just looking for an algorithm that best approximates e in each group? $\endgroup$
    – TheJack
    Aug 15, 2023 at 12:40
  • $\begingroup$ 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 $\endgroup$
    – Orbit
    Aug 15, 2023 at 12:55
  • $\begingroup$ @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 $\endgroup$
    – TheJack
    Aug 15, 2023 at 12:58
  • $\begingroup$ (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. $\endgroup$ Aug 15, 2023 at 13:05

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .