Largest sum of k elements not larger than m

Question

This problem is from a programing competition, and I can't manage to solve it in acceptable time.

You are given an array a of n integers. Find the largest sum s of exactly k elements (not necessarily continuous) that does not exceed a given integer m (s < m).

Constraints:

 0 < k <= n < 100
 m < 3000
 0 < a[i] < 100

Info: A solution is guaranteed to exist for the given input.

Now, I guess my best bet is a DP approach, but couldn't come up with the correct formula.

Answer 1

I would try two things. They are both based on the following idea:

If we can solve the problem of deciding if there are k elements that sum exactly to p, then we can binary search for the answer in [1, m].

1. Optimized bruteforce

Simply sort your array and cut your search short when the current sum exceeds p. The idea is that you will generally only have to backtrack very little, since the sorted array should help eliminate bad solutions early.

To be honest, I doubt this will be fast enough however.

2. A randomized algorithm

Keep a used array of size k. Randomly assign elements to it. While their sum is not p, randomly replace an element with another and make sure to update their sum in constant time.

Keep doing this a maximum of e times (experiment with its value for best results, the complexity will be O(e log m) in the end, so it can probably go quite high), if you couldn't get to sum p during this time, assume that it is not possible.

Alternatively, forget the binary search. Run the randomized algorithm directly and return the largest valid sum it finds in e runs or until your allocated running time ends.

I am not sure how DP would efficiently keep track of the number of elements used in the sum. I think the randomized algorithm is worth a shot since it is easy to implement.

Answer 2

Both of the accepted methods are inferior. Also, this is not a problem type that can be solved by DP.

The following is the correct method illustrated via example:

imagine a = { 2, 3, 5, 9, 11, 14, 17, 23 } (hence n = 8), k = 3, and s = 30

Sort the array a.

Define three pointers into the array, P1, P2, and P3 going from 1 to n. P1 < P2 < P3

Set P3 to a_max (here 23), P1 to 1, and P2 to 2. Calculate the sum s (here 23 + 2 + 3 = 28). If s > S, then decrease P3 by one and try again until you find a solution. If P3 < 3, then there is no solution. Store your first solution as best known solution so far (BKSSF).

Next, increase P2 until s > S. If you find a better solution update BKSSF. Decrease P2 by one.

Next increase P1 until s > S. Update if you find a better solution.

Now go back to P2 and decrease it by one.

Then increase P1 until s > S. etc.

You can see this is a recursive algorithm, in which for every increase or decrease, there is one or more corresponding decreases, increases.

This algorithm will be much, much faster than the attempts above.