How do I find the closest possible sum of an Array

Question

In Java, how should I find the closest (or equal) possible sum of an Array's elements to a particular value K?

For example, for the array {19,23,41,5,40,36} and K=44, the closest possible sum is 23+19=42. I've been struggling on this for hours; I know almost nothing about dynamic programming. By the way, the array contains only positive numbers.

Answer 1

You can see it as a n-choose-k problem for all possible k so the complexity is exponential.

1. Find a set of numbers that sum at most up to K. The set should include i numbers, for i=1; i<=N; i++. To implement this, for each i just take all the n-choose-i combinations of the numbers in the array.
2. Keep a finalResult variable with the best set of numbers found so far and their sum.
3. Compare each sub-result of step 1 with the finalResult and update it if necessary.

It reminds me of the Knapsack problem, so you may want to take a look at it.

Answer 2

I would say first sort the array. Then your example would be: arr = {5, 19, 23, 36, 40, 41}. Then: 1) Take arr[0] and arr[i], where i = arr.Size. Sum it and record the difference between the sum and K, if the sum is lower than K. 2) If sum > K, do step 1, but instead of arr[i], use arr[i-1], because we want to lower our sum. If sum < K, do step 1, but instead of arr[0], use arr[1], because we want to increase our sum. Keep repeating step2, by either increasing or decreasing the indices, until the indices for the two elements are equal. Then, we know the pair of elements that result in the smallest difference between the sum and K.

----------------Edited for arbitrary number of elements in the solution----------------

I believe you may need a tree. Here's what I'm thinking:

1) Choose a number as your top node.

2) For each number in the set, create a child node, and for each branch that was created, calculate the sum of that branch.

3) If the sum is less then K, we branch again, creating child nodes for all the elements in the set. If the sum is greater than K, we stop, keep the difference between the sum and K(If sum < K). If we find a branch with a better sum, then we keep that branch. Repeat this process until all branches are done branching.

Do steps 1-3 with different topnodes.

Answer 3

You would typically use dynamic programming for such a problem. However, that essentially boils down to keeping a set of possible sums and adding the input values one by one, as in the following code, and has the same asymptotic running time: O(n K), where n is the size of your input array and K is the target value.

The constants in the version below are probably bigger, however, but I think the code is much easier to follow, than the dynamic programming version would be.

public class Test {
    public static void main(String[] args) {
        int K = 44;
        List<Integer> inputs = Arrays.asList(19,23,41,5,40,36);

        int opt = 0;                // optimal solution so far          

        Set<Integer> sums = new HashSet<>();
        sums.add(opt);

        // loop over all input values
        for (Integer input : inputs) {
            Set<Integer> newSums = new HashSet<>();

            // loop over all sums so far                        
            for (Integer sum : sums) {
                int newSum = sum + input;

                // ignore too big sums
                if (newSum <= K) {
                    newSums.add(newSum);

                    // update optimum                       
                    if (newSum > opt) {
                        opt = newSum;
                    }
                }
            }

            sums.addAll(newSums);
        }

        System.out.println(opt);
    }
}

EDIT

A short note on running time might be useful, since I just claimed O(n K) without justification.

Clearly, initialization and printing the result just takes constant time, so we should analyse the double loop.

The outer loop runs over all inputs, so it's body is executed n times.

The inner loop runs over all sums so far, which could be an exponential number in theory. However, we use an upper bound of K, so all values in sums are in the range [0, K]. Since sums is a set, it contains at most K+1 elements.

All computations inside the inner loop take constant time, so the total loop takes O(K). The set newSums also contains at most K+1 elements, for the same reason, so the addAll in the end takes O(K) as well.

Wrapping up: the outer loop is executed n times. The loop body takes O(K). Therefore, the algorithm runs in O(n K).

EDIT 2

Upon request on how to also find the elements that lead to the optimal sum:

Instead of keeping track of a single integer - the sum of the sublist - you should also keep track of the sublist itself. This is relatively straightforward if you create a new type (no getters/setters to keep the example concise):

public class SubList {
    public int size;
    public List<Integer> subList;

    public SubList() {
        this(0, new ArrayList<>());
    }

    public SubList(int size, List<Integer> subList) {
        this.size = size;
        this.subList = subList;
    }
}

The initialization now becomes:

SubList opt = new SubList();

Set<SubList> sums = new HashSet<>();
sums.add(opt);  

The inner loop over the sums needs some small adaptations as well:

for (Integer input : inputs) {
    Set<SubList> newSums = new HashSet<>();

    // loop over all sums so far                        
    for (SubList sum : sums) {
        List<Integer> newSubList = new ArrayList<>(sum.subList);
        newSubList.add(input);
        SubList newSum = new SubList(sum.size + input, newSubList);         

        // ignore too big sums
        if (newSum.size <= K) {
            newSums.add(newSum);

            // update optimum                       
            if (newSum.size > opt) {
                opt = newSum;
            }
        }
    }

    sums.addAll(newSums);
}