Algorithm to find the largest of the sums in a list

Question

Algorithm to find the largest of the sums in a list

Navigation

#1 by (2 votes)

2

I need some way to find the best way to find a sum that is closest to an input parameter in a method

      public int MejorSuma(int numero, int suma, List<int> lista) {
            ....
      }

I want to create a function with three parameters;

The "number" parameter determines the number of variables to add to the list.

The "sum" parameter is the maximum value that should be reached, if there is not an exact combination, I should keep the best combination, but never skip over.

The "list" parameter is a list of int.

Example;

    lista = new List<int> {91, 74, 73, 85, 73, 81, 87};
    n = this.MejorSuma(230, 3, lista);

In what "n" should give me a value of 228 , which is the best combination ... I've been trying for several days to find a good solution without " Framing "the program too much.

The list will always have a number of variables greater than the value of the parameter "sum" is where I get stuck, I do not know what algorithm to create to look for all possible combinations ...

c#

asked by Edulon 22.08.2017 в 11:53

source

1 answer

I need you to give me 2 different letters error: ISO C ++ forbids comparison between pointer and integer [-fpermissive]

score 2 · Accepted Answer

In principle, what you are looking for is not very complicated. Perhaps the most complex thing is to find all the combinations of elements in the list taken from n to n. To achieve that, we use the following extension method that makes use of LINQ and recursion:

public static IEnumerable<IEnumerable<T>> Combinaciones<T>(this IEnumerable<T> elementos, int n)
{
    return n == 0 ? new[] { new T[0] } :
        elementos.SelectMany((e, i) =>
        elementos.Skip(i + 1).Combinaciones(n - 1).Select(c => (new[] { e }).Concat(c)));
}

Once we have this method, it is trivial to code the MejorSuma method:

public int MejorSuma(int suma, int numero, List<int> lista)
{
    var combinaciones = lista.Combinaciones(numero);

    int maxsuma = 0;
    foreach (var c in combinaciones)
    {
        int sumaParcial = c.Sum();
        if (sumaParcial>maxsuma && sumaParcial<=suma)
        {
            maxsuma = sumaParcial;
        }
    }
    return maxsuma;
}

Using your data example:

var lista1 = new List<int> { 91, 74, 73, 85, 73, 81, 87 };
int n = this.MejorSuma(230, 3, lista1);
//n=228

The extension method code is taken from this answer