Get closest value from list by summation or exact single value using C#

Question

I want to find the closest transaction amount which is closest(which should be >= transaction amount) or equal to single transaction amount of the given number,but it should be minimum amount. there will be many combination of data which is >= given number but out of those combination I want minimum transaction number.

Let's say I have given amount is 100 and given transaction amount numbers are as below

Scenario 1: 85, 35, 25, 45, 16, 100

Scenario 2: 55, 75, 26, 55, 99

Scenario 3: 99, 15, 66, 75, 85, 88, 5

the expected output of above scenarios are as below

Scenario 1: 100

Scenario 2: 75, 26 (i.e. 75+26=101)

Scenario 3: 85, 15 (i.e. 85+15=100)

My current code is given output as below

Scenario 1: 85, 25

Scenario 2: 55, 26, 55

Scenario 3: 99, 5

Here is my code

class Program
{
    static void Main(string[] args)
    {
        string input;
        decimal transactionAmount;
        decimal element;

        do
        {
            Console.WriteLine("Please enter the transaction amount:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out transactionAmount));

        Console.WriteLine("Please enter the claim amount (separated by spaces)");
        input = Console.ReadLine();

        string[] elementsText = input.Split(' ');
        List<decimal> claimAmountList = new List<decimal>();
        foreach (string elementText in elementsText)
        {
            if (decimal.TryParse(elementText, out element))
            {
                claimAmountList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(transactionAmount, claimAmountList.ToArray());
        foreach (List<decimal> result in results)
        {
            foreach (decimal value in result)
            {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();

    }
    public class Solver
    {

        private List<List<decimal>> mResults;
        private decimal minimumTransactionAmount = 0;
        public List<List<decimal>> Solve(decimal transactionAmount, decimal[] elements)

        {

            mResults = new List<List<decimal>>();
            RecursiveSolve(transactionAmount, 0.0m,
                new List<decimal>(), new List<decimal>(elements), 0);
            return mResults;
        }

        private void RecursiveSolve(decimal transactionAmount, decimal currentSum,
            List<decimal> included, List<decimal> notIncluded, int startIndex)
        {
            decimal a = 0;
            for (int index = startIndex; index < notIncluded.Count; index++)
            {

                decimal nextValue = notIncluded[index];


                if (currentSum + nextValue >= transactionAmount)
                {
                    if (a >= currentSum + nextValue)
                    {
                        if (minimumTransactionAmount < currentSum + nextValue)
                        {
                            minimumTransactionAmount = currentSum + nextValue;
                            List<decimal> newResult = new List<decimal>(included);
                            newResult.Add(nextValue);
                            mResults.Add(newResult);
                        }
                        a = currentSum + nextValue;
                    }
                    if (a == 0)
                    {
                        a = currentSum + nextValue;    
                    }

                }
                else if (currentSum + nextValue < transactionAmount)
                {
                    List<decimal> nextIncluded = new List<decimal>(included);
                    nextIncluded.Add(nextValue);
                    List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                    nextNotIncluded.Remove(nextValue);
                    RecursiveSolve(transactionAmount, currentSum + nextValue,
                        nextIncluded, nextNotIncluded, startIndex++);
                }
            }
        }
    }

}

Answer 1

OK, here I would try to put up some pointers for the answer. Basically, I think it will be best to make some intermediate class and method to help you solving the problem. The idea is as follow:

1. You could make a custom class which has two elements TotalValue and Combinations to store total value and combinations for each combination of number set in your scenario. Something like this

   public class CombinationAndValue {
       public int TotalValue;
       public List<int> Combinations;
   }
   

2. Next, you can make a customized method, which takes a list of values (that is, your number set) as an input and generate all possible CombinationAndValue class' instances.

   public List<CombinationAndValue> comVals(List<int> vals) {
       List<CombinationAndValue> coms = new List<CombinationAndValue>();
       //... logic to generate all possible combinations
       return coms;
   }
   

   To create all possible combinations from a set of item, consider the answers from this link or from some other resources.

3. Once you have both items, you could do simple LINQ to get the solution:

   List<int> vals = new List<int>() { 55, 75, 26, 55, 99 };
   int target = 100;
   CombinationAndValue sol = comVals(target, vals)
                               .Where(x => x.TotalValue >= 100) //take everything that has TotalValue >= 100
                               .OrderBy(x => x.TotalValue) //order by TotalValue from the smallest
                               .ThenBy(x => x.Combinations.Count) //then by the number of combined elements
                               .FirstOrDefault(); //get first or default