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
   

Answer 2

You will probably have to brute-force this. Here's one approach:

Write methods to provide all possible combinations

This is a standard approach using bits set in a uint. Note that this implementation will only support arrays with up to 31 elements. Also, error handling is omitted for brevity.

public static IEnumerable<IEnumerable<T>> Combinations<T>(T[] array)
{
    uint max = 1u << array.Length;

    for (uint i = 1; i < max; ++i)
        yield return select(array, i, max);
}

static IEnumerable<T> select<T>(T[] array, uint bits, uint max)
{
    for (int i = 0, bit = 1; bit < max; bit <<= 1, ++i)
        if ((bits & bit) != 0)
            yield return array[i];
}

Write methods to obtain the "maximum" element of a sequence

For this, we can use Jon Skeet et al's "MaxBy", which I reproduce here for convenience (but it is available via NuGet).

public static TSource MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector)
{
    return source.MinBy(selector, Comparer<TKey>.Default);
}

public static TSource MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector, IComparer<TKey> comparer)
{
    using (IEnumerator<TSource> sourceIterator = source.GetEnumerator())
    {
        if (!sourceIterator.MoveNext())
            throw new InvalidOperationException("Sequence was empty");

        TSource min = sourceIterator.Current;
        TKey minKey = selector(min);

        while (sourceIterator.MoveNext())
        {
            TSource candidate = sourceIterator.Current;
            TKey candidateProjected = selector(candidate);

            if (comparer.Compare(candidateProjected, minKey) < 0)
            {
                min = candidate;
                minKey = candidateProjected;
            }
        }

        return min;
    }
}

Write the algorithm

Having got the boilerplate code out of the way, we can now write the algorithm to determine the closest match:

public static IEnumerable<int> FindClosest(int[] array, int target)
{
    var result = Combinations(array).MinBy(c => {
        int s = c.Sum();
        return s >= target ? s : int.MaxValue; });

    return result.Sum() >= target ? result : Enumerable.Empty<int>();
}

(Be aware that this algorithm enumerates the sequence multiple times, which is fine for an array, but would be bad for general IEnumerable<T>.)

Compilable Demo

Putting this altogether into a compilable demo console app:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    static class Program
    {
        static void Main()
        {
            int target = 100;

            test(85, 35, 25, 45, 16, 100);   // Prints 100: 100
            test(55, 75, 26, 55, 99);        // Prints 101: 75, 26
            test(99, 15, 66, 75, 85, 88, 5); // Prints 100: 15, 85
            test(1, 1, 1, 1, 1);             // Prints 0: 
        }

        static void test(params int[] a)
        {
            var result = FindClosest(a, 100);
            Console.WriteLine(result.Sum() + ": " + string.Join(", ", result));
        }

        public static IEnumerable<int> FindClosest(int[] array, int target)
        {
            var result = Combinations(array).MinBy(c => {
                int s = c.Sum();
                return s >= target ? s : int.MaxValue; });

            return result.Sum() >= target ? result : Enumerable.Empty<int>();
        }

        public static IEnumerable<IEnumerable<T>> Combinations<T>(T[] array)
        {
            uint max = 1u << array.Length;

            for (uint i = 1; i < max; ++i)
                yield return select(array, i, max);
        }

        static IEnumerable<T> select<T>(T[] array, uint bits, uint max)
        {
            for (int i = 0, bit = 1; bit < max; bit <<= 1, ++i)
                if ((bits & bit) != 0)
                    yield return array[i];
        }

        public static TSource MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector)
        {
            return source.MinBy(selector, Comparer<TKey>.Default);
        }

        public static TSource MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector, IComparer<TKey> comparer)
        {
            using (IEnumerator<TSource> sourceIterator = source.GetEnumerator())
            {
                if (!sourceIterator.MoveNext())
                    throw new InvalidOperationException("Sequence was empty");

                TSource min = sourceIterator.Current;
                TKey minKey = selector(min);

                while (sourceIterator.MoveNext())
                {
                    TSource candidate = sourceIterator.Current;
                    TKey candidateProjected = selector(candidate);

                    if (comparer.Compare(candidateProjected, minKey) < 0)
                    {
                        min = candidate;
                        minKey = candidateProjected;
                    }
                }

                return min;
            }
        }
    }
}

Alternative approach using MinByOrDefault

The solution above is complicated by the fact that MinBy doesn't work with empty sequences. We can change it slightly so that it does, and rename it to MinByOrDefault.

With that change, the special case code disappears from FindClosest(), which now returns null if no match is found:

public static IEnumerable<int> FindClosest(int[] array, int target)
{
    return Combinations(array)
        .Where(c => c.Sum() >= target)
        .MinByOrDefault(c => c.Sum());
}

I think this looks rather elegant - but there are probably faster and more efficient (but more complicated) implementations that could be written. In particular, note that the sum is calculated twice for each combination. That could be avoided.

Here's the updated compilable demo program. I like this version better:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    static class Program
    {
        static void Main()
        {
            int target = 100;

            test(85, 35, 25, 45, 16, 100);   // Prints 100: 100
            test(55, 75, 26, 55, 99);        // Prints 101: 75, 26
            test(99, 15, 66, 75, 85, 88, 5); // Prints 100: 15, 85
            test(1, 1, 1, 1, 1);             // Prints 0: 
        }

        static void test(params int[] a)
        {
            var result = FindClosest(a, 100);

            if (result != null)
                Console.WriteLine(result.Sum() + ": " + string.Join(", ", result));
            else
                Console.WriteLine("No result found for: " + string.Join(", ", a));
        }

        public static IEnumerable<int> FindClosest(int[] array, int target)
        {
            return Combinations(array)
                .Where(c => c.Sum() >= target)
                .MinByOrDefault(c => c.Sum());
        }

        public static IEnumerable<IEnumerable<T>> Combinations<T>(T[] array)
        {
            uint max = 1u << array.Length;

            for (uint i = 1; i < max; ++i)
                yield return select(array, i, max);
        }

        static IEnumerable<T> select<T>(T[] array, uint bits, uint max)
        {
            for (int i = 0, bit = 1; bit < max; bit <<= 1, ++i)
                if ((bits & bit) != 0)
                    yield return array[i];
        }

        public static TSource MinByOrDefault<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector)
        {
            return source.MinByOrDefault(selector, Comparer<TKey>.Default);
        }

        public static TSource MinByOrDefault<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector, IComparer<TKey> comparer)
        {
            using (IEnumerator<TSource> sourceIterator = source.GetEnumerator())
            {
                if (!sourceIterator.MoveNext())
                    return default(TSource);

                TSource min = sourceIterator.Current;
                TKey minKey = selector(min);

                while (sourceIterator.MoveNext())
                {
                    TSource candidate = sourceIterator.Current;
                    TKey candidateProjected = selector(candidate);

                    if (comparer.Compare(candidateProjected, minKey) < 0)
                    {
                        min = candidate;
                        minKey = candidateProjected;
                    }
                }

                return min;
            }
        }
    }
}

Addendum

Here's a version of FindClosest() which doesn't compute the sum twice. It's not as elegant, but will probably be faster:

public static IEnumerable<int> FindClosest(int[] array, int target)
{
    return Combinations(array)
        .Select(c => new {S = c.Sum(), C = c})
        .Where(c => c.S >= target)
        .MinByOrDefault(x => x.S)
        ?.C;
}

Combinations of more than 31 items

This version of Combinations() will work for up to 63 items:

public static IEnumerable<IEnumerable<T>> Combinations<T>(T[] array)
{
    ulong max = 1ul << array.Length;

    for (ulong i = 1; i != max; ++i)
        yield return selectComb(array, i);
}

static IEnumerable<T> selectComb<T>(T[] array, ulong bits)
{
    ulong bit = 1;

    for (int i = 0; i < array.Length; bit <<= 1, ++i)
        if ((bits & bit) != 0)
            yield return array[i];
}

I think it's unlikely that you will want to generate all the combinations of more than 63 items.

After all, 63 items have 2^63 combinations, or 9,223,372,036,854,775,808 combinations.

Even if you could process a billion of those a second, it would take you more than 250 years to do so...

Answer 3

As it has been noted in the comments this is a variation of the knapsack problem. However, as described in the question Variation on knapsack - minimum total value exceeding 'W' your problem is in a sense the converse of a knapsack problem because you want to minimize the weight of the items subject to a constraint that the total weight should exceed a minimum value. In a knapsack problem you want to maximize the weight subject to a constraint that the total weight cannot exceed a maximum value.

Fortunately, the accepted answer demonstrates how a "converse knapsack problem" can be solved by putting items (transaction values) into a knapsack. The items (transaction values) that could not fit into the knapsack are then an optimal solution to your problem.

Google's Operations Research tools provide .NET bindings for algorithms to solve the knapsack problem. Start with the input to the algorithm:

var amounts = new[] { 55, 75, 26, 55, 99 };
var targetAmount = 100;

Create a knapsack solver:

const String name = "https://stackoverflow.com/questions/36195053/";
var solver = new KnapsackSolver(
  KnapsackSolver.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
  name
);

The algorithm type is chosen here and as the size of the input increases some algorithms may have better performance so you may need to make adjustments here, in particular when the brute force algorithm begins to perform badly. (Solving the knapsack problem is NP hard.)

Convert the input to values used by the knapsack solver:

var profits = amounts.Select(amount => (Int64) amount).ToArray();
var weights = new Int64[1, profits.Length];
for (var i = 0; i < profits.Length; i += 1)
  weights[0, i] = profits[i];
var capacities = new Int64[] { amounts.Sum() - targetAmount };

Notice how the capacity is set to the sum of all the weights minus the target value as described by amit.

Execute the solver:

solver.Init(profits, weights, capacities);
solver.Solve();
var solution = profits
  .Where((profit, index) => !solver.BestSolutionContains(index))
  .Select(profit => (Int32) profit)
  .ToArray();

The amounts that did not make it into the knapsack are the solution values. In this case 75, 26 as expected.

Answer 4

Assuming optimisation isn't an issue, problems like this always are easiest to do with brute force. In the case of this, just try every combination of the number pairs, and find the one that gives you the lowest result.

Heres with I came up with:

    public List<List<decimal>> Solve(decimal transactionAmount, decimal[] elements)
{
    int combinations = Convert.ToInt32(Math.Pow(2.0, elements.Length));
    List<List<decimal>> results = new List<List<decimal>>();
    List<decimal> result = new List<decimal>();
    decimal bestResult = elements.Sum();
    for (int j = 0; j < combinations; j++)
    {
        string bitArray = Convert.ToString(j, 2).PadLeft(elements.Length, '0');
        decimal sum = 0;
        for (int i = 0; i < elements.Length; i++)
        {
            sum += bitArray[i].Equals('1') ? elements[i] : 0;
            if (sum > bestResult)
                break;
        }

        if (sum > bestResult || sum < transactionAmount)
            continue;

        result.Clear();
        result.AddRange(elements.Where((t, i) => bitArray[i].Equals('1')));
        bestResult = result.Sum();

        //Perfect result
        if (sum == transactionAmount)
            results.Add(new List<decimal>(result));
    }

    // Get last solution
    if (results.All(x => result.Except(x).ToList().Count != 0))
        results.Add(new List<decimal>(result));

    return results;
}

It simply tracks the sum of the numbers as a binary number, which tells it to either add or not add. If it finds a solution which is better than the current one, it updates it. Otherwise just loops around to try the next combination.

I actually had a similar problem to do when I was in university, so i know there are a few optimisations for this specific kind of problem. I put the only one I remembered in, which is no need to keep calculating the sum, if it is already worse than your best result.

EDIT: Just modified it to return more than 1 solution, because I noticed you had a List of List. In case you are wondering about the new List, its to make the List get a copy rather than a pointer to the result (which is changing).

EDIT2: I realized you could get duplicate solutions (say if you have 50, 50, 50, 50). If you want to avoid those, you can do this:

public List<List<decimal>> Solve(decimal transactionAmount, decimal[] elements)
{
    // ....
    for (int j = 0; j < combinations; j++)
    {
        // ....
        //Perfect result
        if (sum == transactionAmount)
            results.Add(new List<decimal>(result.OrderBy(t => t)));
    }
    results.Add(new List<decimal>(result.OrderBy(t => t)));

    return results.Distinct(new ListDecimalEquality()).ToList();
}

public class ListDecimalEquality : IEqualityComparer<List<decimal>>
{
    public bool Equals(List<decimal> x, List<decimal> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode(List<decimal> obj)
    {
        int hashCode = 0;

        for (int index = 0; index < obj.Count; index++)
        {
            hashCode ^= new { Index = index, Item = obj[index] }.GetHashCode();
        }

        return hashCode;
    }
}

Answer 5

You can try this simple method:

int[] A = {99, 15, 66, 75, 80, 5, 88, 5};
List<Tuple<string, int>> list = new List<Tuple<string, int>>();
list.Add(new Tuple<string, int>(A[0].ToString(),A[0]));
for(int i = 1; i < A.Length; i++)
{
    var newlist = new List<Tuple<string, int>>();
    list.ForEach(l=>newlist.Add(new Tuple<string, int>(l.Item1 + " " + A[i],l.Item2 + A[i])));
    list.Add(new Tuple<string, int>(A[i].ToString(),A[i]));
    list.AddRange(newlist);
}

Tuple<string, int> solution = list.Where(l =>l.Item2 >= 100).OrderBy(o=>o.Item2).First();