Найти элементы, сумма которых ближе всего к заданному значению

Question

Я искал и читал об алгоритмах для этой проблемы, но они, похоже, не применяются в этом случае или недостаточно ясны.

У меня есть List<decimal>из неподписанных значения, где я пытаюсь найти элемент (ы), который суммы является ближайшей к определенному значению N

Список имеет переменного размера с средним 500 элементов. Производительность НЕ является приоритетом для этого решения.

Внедренный метод должен возвращать одно решение или пустой список, если решение не найдено.

Существующие более одного, выберите один с меньшим количеством элементов.

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 

Answer 1

Это решение может быть решено линейно по времени с использованием подхода dynamic programming.

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); 
    } 

Answer 2

Во-первых, добавить этот удобный расширение Combination: (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))); 
    } 
} 

И потом:

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[] { }; 
} 

Answer 3

Я набранный в каком-то старомодно, но работает отлично!

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; 
    }