Optimizing Subset selection algorithm to compare solutions within a deviation

Question

I'm currently using a algorithm to find the element(s) (unsigned decimals) which sum is the closest to a specified value target. EDIT: Elements can only be used once.

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

Existing more than one solutions, I need to get the one with the less elements. I've been analyzing the code but can not conclude whether that is the case.

Even better, but probably more difficult to accomplish would be to select the solution with less elements within a range.

Eg:

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

I'm looking for help on how to optimize this algorithm to accomplish the changes above. Thanks!

Answer 1

Try a recursive algorithm. The code at level 0 tries 10, 20, 30, 40. At level 2 tried two numbers like 10, 20 then 10, 30, and then 10, 40. The code has a feature that is stops trying when at a level the sum is greater than the target.

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