找出和最接近给定值的元素

本文关键字：元素 最接近 | 更新日期: 2023-09-27 17:49:24

我已经搜索并阅读了关于这个问题的算法，但它们似乎不适用于这种情况，或者不够清楚。

我有一个unsigned值的List<decimal>，我试图找到和最接近指定值N的元素(s)

List的大小是可变的，平均有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

找出和最接近给定值的元素

首先，添加这个方便的组合扩展:(归功于这个答案)

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

这可以用动态规划方法在时间线性上求解。

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

我用一种老式的方式输入，但效果很好!

    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;
    }
相关文章：