0

Given a list of integers, I have to maximize the sum of product of cardinality of the each subsets into the sum of the corresponding subset.

For eg - $A : -1,-2-3,2,1,3,100$.

Then maximum sum can be obtained by using the whole list as 1 set instead of breaking into subsets i.e $(100(sum)*7(cardinality))$

I could think of considering every combination of subsets. I was also thinking to take all positives into single set and each negative as an individual set but this won't give optimal answer.

Is there an efficient way to find subsets ?

Bash
  • 13
  • So you break the list into subsets, sum each subset, multiply that sum by the cardinality of the subset, and sum the products? If we split A as $(-1,-2),(-3,2,1,3),(100)$ we would compute $ (-1+(-2))\cdot 2 + (-3+2+1+3)\cdot 4 + 100 \cdot 1?$ – Ross Millikan Jun 04 '17 at 22:56
  • Well you are trying to maximize. So for any proper subset just remove the lowest terms to maximize the sum. So you have $7100$ vs $6103$ vs $5101$ etc. The (slightly) hard part is detrimining if $nsum$ is greater or less than $(n-1)(sum - min)$ It can only be more if $min$ is negative. $n|min|-|min| > sum$. So as $37 < 100$ the max is the entire set. But the set {-4, 2,5,6 } then $sum = 9$, $n=4$, |min|=4 and $44-4 > 9$ so {2,5,6} => $313 = 39 > 4*9 = 36$. – fleablood Jun 05 '17 at 00:23
  • @RossMillikan Yes exactly ! – Bash Jun 05 '17 at 08:18
  • @fleablood You also have to take into consideration the sum of remaining set as all elements have to be taken care of i.e $((7100)+(00)) vs (6103)+((-3)1) vs (5101)+(-21)+(11)$. Also can you elaborate on determining the part where $nsum$ is greater or less than$ (n−1)(sum−min) $ ? I couldn't grasp it properly. – Bash Jun 05 '17 at 08:25

1 Answers1

1

Clearly all the positive elements should go in one subset to get the multiplier as high as possible. All the negative elements that are not in that subset should go in singletons to make the multiplier as small as possible. The only question is which negative elements should be in the set with the positives. Start with all the elements in one set and compare with taking the most negative number out to its own set. If that improves the result, try taking out the next most negative number. Keep going until the result doesn't improve and you have the optimum.

Ross Millikan
  • 374,822
  • Thanks, I was thinking of this only as I mentioned in my question but couldn't think of how to eliminate negative integers to maximize it. – Bash Jun 06 '17 at 08:10