Find elements which sum is closest to a given value

Question

I have searched and read about algorithms for this problem but they don't seem to apply in this case, or were not clear enough.

I have a List<decimal> of unsigned values where I'm trying to find the element(s) which sum is the closest to a specified value N

The List is of variable size with average of 500 elements. Performance is NOT a priority for this solution.

The implemented method should return a single solution or an empty list if no solution is found.

Existing more than one, pick one with the less elements.

Example:

N = 15.00

Elements = {
0.10, //EDIT: This shouldn't be here
7.00,
7.00,
14.10,
15.90,
}

Solutions = {
0.10 + 7.00 + 7.00, //EDIT: This shouldn't be here
14.10,
15.90,
} 

Final Solution = {14.10} // or 15.90

This needs more clarification. What are the possible solutions for an answer? Any combination of any of the numbers in Element? If so, your final solution doesn't make sense because 14.10 + 0.10 would be 14.20, which is closer to 15 than 14.10 is. — Francine DeGrood Taylor, May 15 '15 at 22:53
I'm pretty sure `{14.10 + 0.10}` is better than your proposed "correct" answer. Anyway dynamic programming gets this done very efficiently. Pruned dynamic programming, even moreso. — Ben Voigt, May 15 '15 at 22:54
This is very closely related to the [Knapsack Problem](http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem), and the same approach will work (with a small modification to change the hard limit to a soft limit) — Ben Voigt, May 15 '15 at 23:01
Branch and bound solution could be effective, but any exact solution will be O(2^n) due to the fact that this is effectively subset sum. — AndyG, May 16 '15 at 00:05
I hope this stays open, I'd like to see a `C#` implementation. — John Alexiou, May 16 '15 at 01:51

score 2 · Answer 1 · edited May 23 '17 at 10:32

First, add this handy Combination extension: (credits to this answer)

public static class EnumerableExtensions
{
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
    {
        return k == 0 ? new[] { new T[0] } :
          elements.SelectMany((e, i) =>
            elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
    }
}

And then:

private IEnumerable<decimal> ClosestSum(decimal[] elements, decimal n)
{
    var target = Enumerable.Range(1, elements.Length)
        .SelectMany(p => elements.Combinations(p))
        .OrderBy(p => Math.Abs((decimal)p.Sum() - n))
        .ThenBy(p => p.Count())
        .FirstOrDefault();
    return target ?? new decimal[] { };
}

droid · Answer 2 · 2015-05-15T23:57:57.270

1

This can be solved in time linear with respect to the input with a dynamic programming approach.

    private class Solution
    {
        public int StartIndex;
        public int EndIndex;
        public decimal Sum;
        public int Length
        {
            get { return EndIndex - StartIndex + 1; }
        }

    }

    static List<decimal> Solve(List<decimal> elements, decimal target)
    {
        Solution bestSolution = new Solution { StartIndex = 0, EndIndex = -1, Sum = 0 };
        decimal bestError = Math.Abs(target);
        Solution currentSolution = new Solution { StartIndex = 0, Sum = 0 };

        for (int i = 0; i < elements.Count; i++)
        {
            currentSolution.EndIndex = i;
            currentSolution.Sum += elements[i];
            while (elements[currentSolution.StartIndex] <= currentSolution.Sum - target)
            {
                currentSolution.Sum -= elements[currentSolution.StartIndex];
                ++currentSolution.StartIndex;
            }
            decimal currentError = Math.Abs(currentSolution.Sum - target);
            if (currentError < bestError || currentError == bestError && currentSolution.Length < bestSolution.Length )
            {
                bestError = currentError;
                bestSolution.Sum = currentSolution.Sum;
                bestSolution.StartIndex = currentSolution.StartIndex;
                bestSolution.EndIndex = currentSolution.EndIndex;
            }
        }

        return elements.GetRange(bestSolution.StartIndex, bestSolution.Length);
    }

edited May 15 '15 at 23:57

answered May 15 '15 at 23:02

droid

291
2
5

"in linear time"... linear in *what*? Not in the number of elements in the input set. – Ben Voigt May 15 '15 at 23:05
The memory requirement isn't O(1) either, since you have to store a list. – Ben Voigt May 15 '15 at 23:07
In fact, the only part of your answer that's right are the words "dynamic programming". Ohhh, I see, you're assuming runs of adjacent elements. I can't tell whether the problem actually is restricted to adjacent runs or not. – Ben Voigt May 15 '15 at 23:10
replaced rough draft proof with code, if shardl wants subsequence then @Gabriel has the correct answer – droid May 16 '15 at 00:00
I've tested this and it seems to work, but just looking at the code I can't determine if this returns the solution with least elements. – bockzior Jun 02 '15 at 22:54
But what if have array [10,1,30,40,50] and the number i want to find is 4? the closest should be 1 ? but it resturn empty result. How to fix it? – Enteee Aug 12 '16 at 22:08

score 1 · Answer 3 · answered May 16 '15 at 00:21

I typed in some old-fashioned way, but works perfectly!

    bool InRange(decimal num, decimal value, decimal range)
    {
        return ((num >= value - range) && (num < value + range));
    }

    decimal GetClosestSum(decimal value, List<decimal> elements, decimal range)
    {
        elements.Sort();
        var possibleResults = new List<decimal>();
        for (int x = elements.Count - 1; x > 0; x--)
        {
            if (InRange(elements[x], value, range)) possibleResults.Add(elements[x]);
            decimal possibleResult = elements[x];
            for (int i = x - 1; i > -1; i--)
            {
                possibleResult += elements[i];
                if (possibleResult > (value + range - 1)) possibleResult -= elements[i];
                if (InRange(possibleResult, value, range)) possibleResults.Add(possibleResult);
            }
        }
        decimal bestResult = -1;
        for (int x = 0; x < possibleResults.Count; x++)
        {
            if (bestResult == -1)
                bestResult = possibleResults[x];
            if (Math.Abs(value - possibleResults[x]) < Math.Abs(value - bestResult))
                bestResult = possibleResults[x];
        }
        return bestResult;
    }

Find elements which sum is closest to a given value

3 Answers3