优化子集选择算法，在偏差范围内比较解决方案

Question

我目前正在使用一种算法来查找元素(无符号小数)，其中和最接近指定值target。编辑:元素只能使用一次。

private class Solution
{
    public int StartIndex;
    public int EndIndex;
    public decimal Sum;
    public int Length
    {
        get { return EndIndex - StartIndex + 1; }
    }
}
public 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);
}

存在多个解，我需要得到元素较少的解。我一直在分析代码，但不能断定是不是这样。

更好，但可能更难完成的是选择一个范围内元素较少的解。

,

Target value = 50.00
Solution A: 4 elements => 50.00
Solution B: 3 elements => 49.99
solution C: 2 element  => 49.90    ««« PREFERABLE (Less elements within a given 0.50 deviation )
Solution D: 1 elements => 49.30

我正在寻找如何优化这个算法来完成上面的更改的帮助。谢谢!

Answer 1

尝试递归算法。级别0的代码尝试10,20,30,40。在第二级尝试了两个数字，比如10,20,10,30,10,40。该代码有一个特性，当在某个级别上的和大于目标时停止尝试。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<decimal> inputs = new List<decimal> { 10, 20, 30, 40 };
            int startIndex = 0;
            decimal target = 50;
            Solution solution = new Solution(inputs);
            List<decimal> elements = new List<decimal>();
            solution.Solve(elements, target, startIndex);
        }
        public class Solution
        {
            private List<decimal> inputs = null;
            private static bool first = true;
            public static decimal Sum = -1;
            public static decimal error = -1;
            public static List<decimal> elements { get; set; }
            public Solution(List<decimal> inputs)
            {
                elements = new List<decimal>();
                this.inputs = new List<decimal>(inputs);
                this.inputs.Sort();
            }
            public static bool BestSolution(List<decimal> newSolution, decimal target)
            {
                bool higher = false;
                if(first == true)
                {
                    AddSolution(newSolution, target);
                    first = false;
                }
                else
                {
                    decimal newError = Math.Abs(newSolution.Sum() - target);
                    if(newError < error)
                    {
                        AddSolution(newSolution, target);
                    }
                    else
                    {
                        if((newError == error) && (newSolution.Count < elements.Count))
                        {
                            AddSolution(newSolution, target);
                        }
                    }
                }
                if(elements.Sum() >= target) higher = true;
                return higher;
            }
            private static void AddSolution(List<decimal> newSolution, decimal target)
            {
                Sum = newSolution.Sum();
                error = Math.Abs(newSolution.Sum() - target);
                elements = new List<decimal>(newSolution);
            }
            public void Solve(List<decimal> localElements, decimal target, int startIndex)
            {
                for (int i = startIndex; i < inputs.Count; i++)
                {
                    List<decimal> newElements = new List<decimal>(localElements);
                    newElements.Add(inputs[i]);
                    bool higher = Solution.BestSolution(newElements, target);
                    if (!higher)
                    {
                        Solve(newElements, target, i + 1);
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    }
}