Alex Rivera | Logout

Maximizing the number of combinations of a sum of integers

Asked 2011-10-28T06:27:07.920
14

Basically, given a sorted list of positive non-zero numbers, say {1, 4, 5}, change a single number in the list to maximize the distinct combinations possible. The above gives 1, 4, 5, 6, 9, 10, that is, six combinations. If we were to change 4 to 2 so we have {1, 2, 5}, we'd get 1, 2, 3, 5, 6, 7, 8, that is, seven combinations.

I need to find a number x to add to a single number of the list to maximize the amount of combinations. x should be the smallest abslout value, we can both add or subtract.

I've done it using brute force by enumeration, which runs in many times exponential time. So it's not feasible for larger problems. Now I need to do it fast.

Just checking the number of combinations is exponential time? And I have to find the exact optimal solution.

What would be some keywords for solving this problem? I've attempted to find a recurrence, so I could use dynamic programming and some sort of branch and bound to limit the explosion, but it's no use.

I've looked into problems like cutting mill, subset sum, and a lot of other combinatorial optimization problems to see if I could find some ideas. But I don't get it. Simply verifying the solution is exponential time.

optimization combinatorics
Edit
Report

1 Answer

0

Suppose the question had been: for any value of n, what n positive integers give the maximum number of combinations. The answer to this question is: 2^0, 2^1, 2^2, ... 2^(n-1).

The proof is straightforward because:

  • with this set you can create every integer between 2^0 and (2^n)-1.

  • this set sums to (2^n)-1.

Consider {1, 2, 4}. The combination are: 1, 2, 1+2, 4, 1+4, 2+4 and 1+2+4. 1+2+4 = 7.

It seems reasonable to suggest that for any set you maximise the number of combinations by making the set as similar as possible to 2^0, 2^1, ...

I am not sure what "as similar as possible" means. However, {1, 2, 5} is closer to {1, 2, 4} that {1, 4, 5}. Is this true of the other sets you have investigated by brute force?

I notice that {1, 2, 5} is one away from {1, 2, 4} and has one less combination. Is this a coincidence?

If these observations stand up to examination, I suspect they will not be too difficult to prove. Even if you cannot prove them, they may give you an algorithm that works.

answered 2011-12-21T22:14:18.827

Your Answer