Sélection d'éléments dans une liste pour obtenir une somme

Question

J'ai une liste d'éléments qui ont des valeurs numériques et j'ai besoin de faire une somme en utilisant ces éléments. J'ai besoin de votre aide pour construire un tel algorithme. Ci-dessous, il est un exemple qui décrit mon problème, écrit en C#:

int sum = 21; 

List<Item> list = new List<Item>(); 
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 }); 
list.Add(new Item() { Id = Guid.NewGuid(), Value = 5 }); 
list.Add(new Item() { Id = Guid.NewGuid(), Value = 12 }); 
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 }); 
list.Add(new Item() { Id = Guid.NewGuid(), Value = 2 }); 
list.Add(new Item() { Id = Guid.NewGuid(), Value = 7 }); 

List<Item> result = // the items in the list that has the defined sum. 

Note: Je n'ai aucune contrainte sur le nombre d'éléments dans le résultat.

Answer 1

Ceci est appelé le Subset sum problem et est considéré comme un problème difficile dans la science informatique. Pas difficile comme dans difficile à faire, mais difficile à faire rapide - vous pouvez facilement écrire un algorithme pour le faire, mais pour les entrées importantes, il faudra facilement des milliards d'années.

Si vous êtes heureux avec une solution lente qui est seulement possible pour les petites entrées, essayer quelque chose comme ceci:

• tous les sous-ensembles de Generate la liste d'entrée.

• Pour chaque sous-ensemble, calculez la somme des éléments de ce sous-ensemble.

• Renvoie le premier sous-ensemble pour lequel la somme correspond.

Voici une méthode qui retourne tous les sous-ensembles (en fait sousséquences car elle maintient l'ordre des éléments, bien que dans votre cas cela ne fait aucune différence):

/// <summary> 
/// Returns all subsequences of the input <see cref="IEnumerable&lt;T&gt;"/>. 
/// </summary> 
/// <param name="source">The sequence of items to generate 
/// subsequences of.</param> 
/// <returns>A collection containing all subsequences of the input 
/// <see cref="IEnumerable&lt;T&gt;"/>.</returns> 
public static IEnumerable<IEnumerable<T>> Subsequences<T>(
     this IEnumerable<T> source) 
{ 
    if (source == null) 
     throw new ArgumentNullException("source"); 
    // Ensure that the source IEnumerable is evaluated only once 
    return subsequences(source.ToArray()); 
} 

private static IEnumerable<IEnumerable<T>> subsequences<T>(IEnumerable<T> source) 
{ 
    if (source.Any()) 
    { 
     foreach (var comb in subsequences(source.Skip(1))) 
     { 
      yield return comb; 
      yield return source.Take(1).Concat(comb); 
     } 
    } 
    else 
    { 
     yield return Enumerable.Empty<T>(); 
    } 
} 

Vous pouvez maintenant écrire quelque chose comme ça ...

var result = list.Subsequences() 
       .FirstOrDefault(ss => ss.Sum(item => item.Value) == sum); 

Answer 2

Je ne sais pas exactement quel soleil vous êtes après ici. Si vous voulez que la somme de toutes les valeurs moissonneuses-batteuses, utilisez ce code:

int result = list.Sum(i => i.Value); 

Si vous voulez que tous les éléments qui a une valeur spécifique, utilisez ce code:

int x = 3; 
List<Item> result = list.Where(i => i.Value == x); 

Answer 3

récursive, ajouter des éléments jusqu'à ce que A) vous obtenez la somme ou B) vous obtenez trop, si A vous avez terminé, si B vous changez les éléments en essayant toutes les configurations possibles. Peut-être interdire le système d'ajouter un élément si l'élément courant est déjà plus grand que le dernier élément qui est allé la somme

Answer 4

ce qu'on appelle le problème de la somme sous-ensemble, avec la modification - que vous ne voulez pas arriver à zéro, mais à un particulier nombre.

Voici ce que Wiki a à dire à ce sujet - http://en.wikipedia.org/wiki/Subset_sum_problem.

Vous pouvez penser à certaines optimisations en fonction de vos connaissances du domaine. Par exemple, si le nombre le plus élevé + le nombre le plus bas est supérieur à la somme -> le nombre le plus élevé ne sera jamais utilisé, et vous pouvez l'exclure (et essayez la même chose pour le nouveau nombre le plus élevé ..). Je me souviens de l'avoir fait comme Samuel le suggérait - la manière récursive, qui n'était pas si terrible, (mais bien sûr, il y a toujours le problème de stackoverflow ...).