Given a set of integers L and an integer K, select a minimal subset S of L such that SUM(S) >= K

Question

Problem was a little too long for the title, so here is the exact definition:

Input

Set of integers, L

Integer, K

Output

A subset of L such that:

• The sum of the subset is >= K
• The number of elements in the subset is minimized
• If multiple subsets both meet the above criteria, the subset with the lowest maximum value is preferred.
• If multiple subsets are still tied, the one with the lowest sum is preferred.

e.g.

Input

L = { 4, 2, 3, 1 }

K = 5

The first two criteria would yield {4, 2}, {4, 3}, {4, 1}, and {2, 3}. We would prefer {2, 3} since its maximum value (3) is least of those.

Return null or throw and exception if there is no subset that meets the criteria.

I'm a little worried that this problem is too related to the subset-sum problem and might be NP-complete.

Answer 1

A solution might be the following:

(1) Sort L to get l_1, l_2, ..., l_n, with l_1 > l_2 > ... > l_n.

(2) For k=1,2,...,n, check whether (l_1+...+l_k) >= K, stop for the smallest k.

Now you have the minimal number of elements required to meet the first criteria, and an example set {l_1,...,l_k}.

(3) Now we have to find a set with k elements that satisfies the rest. You could e.g. start by summing up

l_n + l_(n-1) + ... + l_(n-k), then 
l_(n+1) + l_n + ... + l_(n-k+1), then 
l_(n+2) + l_n + ... + l_(n-k+2), ...

and stop whenever one of these sums exceeds or is equal to K.

(1) can be done in O(n*log(n)) time, (2) can be done in O(n) time. (3) can be done in O(n*k) = O(n^2) time. However, this can be improved by using a "telescope sum":

• Compute x := l_n + l_(n-1) + ... + l_(n-k).
• If x < K, then compute x := x - l_n + l_(n-k+1)
• If x < K, then compute x := x - l_(n-1) + l_(n-k+2) etc.

So (3) can be done in O(n), as it seems.

So in total, O(n*log(n)) seems possible for this task.

Answer 2

It seems pretty easy. Sort L and find the first n elements of L that add up to K. That's it. Finding any elements beyond the nth element is not any better, though you might be able to trim off the first few elements. If SUM(L) is less than K, then return null or throw an exception.

Answer 3

Finding the size of the subset is trivial, you can sort the values in reverse order and then find the first partial sum which is greater than or equal to K. This is bounded by the sorting time, which is O(n log n).

In your "greater than or equal to" variant of the subset sum problem, once you find a solution with sum S, you still need to ask "does there exist a subset of length n which has a sum between K and S?" Applying this repeatedly will eventually yield the question "does there exist a subset of length n which has a sum of K?" You can't say that your solution is optimal without answering this question.

The fixed-size subset sum decision problem is NP-complete (since there are only n possible lengths and if this sub-problem was not NP-complete, neither would be the subset sum decision problem).

Answer 4

Here is an algorythm:

1. Sort L in reverse order.
2. Use recursive function to iterate over every possible combination
3. Stop recursion if sum is greater than or equals to K
4. Iterate over resulting subsets and select one with the maximum sum of elemets

Recursion is as follows in Java

private List<Integer> numbers = Arrays.asList(5, 4, 3, 2, 1);
private List<List<Integer>> combinations = new ArrayList<>();

public void selectCombinations(int position, List<Integer> currentCombination) {
    if (position >= numbers.size()) {
        return;
    }
    //next number
    selectCombination(position + 1, currentCombination);

    List<Integer> newCombination = new ArrayList<>(currentCombination);
    newCombination.add(numbers.get(position));
    int sum = ...;//sum of copy
    if (sum >= K) {
        combinations.add(newCombination);
    } else {
         selectCombination(position + 1, newCombination);
    }
}