hi j'ai une liste Je peux également utiliser les fonctions résultats souhaités:
Évidemment, je voudrais quelque chose avec le coût de performance le plus bas possible. linq pour filtrer ou manipuler la liste.
5 Réponses :
Ceci est le problème du sous-ensemble Sous-ensemble , un cas particulier du problème du sac à dos. C'est dur (NP-complet). Les algorithmes les plus connus ont une complexité exponentielle. Cependant, il y a des algorithmes approximatifs avec une complexité polynomiale. Celles-ci répondent à la question «Y a-t-il un sous-ensemble qui sommeille à 1 ± ε?
Ce n'est pas un problème de somme sous-ensemble, cela est plus difficile que le Sous-Sum (car dans le sous-ensemble, vous travaillez avec des entiers, mais ici, vous travaillez avec des points flottants).
mise à jour - maintenant ne résiste pas de manière répétée
Essayez ceci modifier 5ème test
Pouvez-vous le tester avec le 5ème résultat attendu (voir la question modifiée)?
@DAVIDB Le code raccourcit le moment où un résultat est trouvé et prend des douleurs aux branches de coupe courtes qui ne peuvent pas produire de résultat et seront donc mieux que de résumer toutes les permutations. L'utilisation des opérateurs de prise et de saut signifie que l'évaluation de la liste est différée jusqu'à ce que nécessaire. Les opérations de somme sont le point lent actuel
@Davidb La nouvelle mise à jour se débarrasse également de la somme excessive en passant les sommes autour des sommes.
Oui bon travail Bob Vale! Exactement ce que je cherchais..works génial!
Selon la taille de votre liste, quelques optimisations sont possibles. 1ère option: Convertir en tableau avant de tester si vous n'êtes pas une liste ou une matrice. 2ème, invoquer le nombre () une fois et utiliser une seconde surcharge pour transporter cela, sur un véritable énumérable, le nombre peut être très coûteux. 3ème, commandez la liste afin que vous puissiez supprimer / ignorer tout élément trop grand de toute façon. Ensuite, éventuellement optimiser en choisissant le choix du point de départ opportun.
List<decimal> list1 = new List<decimal>(){0.7m, 0.7m, 0.7m};
List<decimal> list2 = new List<decimal>(){0.7m, 0.3m, 0.7m};
List<decimal> list3= new List<decimal>(){0.777777m, 0.2m, 0.1m};
List<decimal> list4 = new List<decimal>() { 0.33333m, 0.33333m, 0.33333m };
List<decimal> list5 = new List<decimal>() { 0.4m, 0.5m, 0.6m, 0.3m };
Console.WriteLine(list1.SubListAddsTo(1m, 0.001m)); //false
Console.WriteLine(list2.SubListAddsTo(1m, 0.001m)); //true
Console.WriteLine(list3.SubListAddsTo(1m, 0.001m)); //false
Console.WriteLine(list4.SubListAddsTo(1m, 0.001m)); //true
Console.WriteLine(list5.SubListAddsTo(1m, 0.001m)); //true
Pouvez-vous le tester avec le 5ème résultat attendu (voir la question modifiée)?
C'est O (2 ^ N) car le numéro suivant peut doubler le nombre de sommes. Cependant, pour les petites listes - pas un problème. Pour les listes avec de nombreuses valeurs largiques (ci-dessus cible / 2), beaucoup de ces sommes sont suffisamment grandes pour ignorer. De plus, sortent dès que la somme cible est trouvée au lieu de vérifier toutes les combinaisons. Enfin, le hashSet élimine les valeurs de somme en double.
Voici une approche assez simple, Niave et forcée brute. Ce ne sera pas efficace, mais j'espère qu'il est plus facile de comprendre.
J'ai comparé les solutions et il s'avère que les méthodes de force brute apparemment naïve étaient les plus rapides. J'ai révisé ma solution pour emprunter une partie du vôtre à proposer le plus rapide, bien que cela ne soit pas aussi lisible que votre solution d'origine.
édité: strong> Mon code d'origine n'a pas permis l'approximation (0,9999 = 1). Ceci utilise un bitmap du nombre de variations pour masquer les valeurs du tableau source dans l'ordre à la force brute toutes les variations. P> Ceci est environ 7,5 fois plus rapide que la réponse acceptée lors de l'essai sur les cinq cas de test dans un million de boucles de comptage (environ 41 secondes VS environ 5,5 secondes). Il s'agit d'environ deux fois plus vite que la SLN de David B et d'environ 15% plus rapide que la SLN de Servy. P> private const decimal Epislon = 0.001m;
private const decimal Upper = 1 + Epislon;
private const decimal Lower = 1 - Epislon;
private static bool NewTest(decimal[] list)
{
var listLength = list.Length;
var variations = (int)(Math.Pow(2, listLength) - 1);
for (var variation = variations; variation > 0; variation--)
{
decimal sum = 0;
int mask = 1;
for (var bit = listLength; bit > 0; bit--)
{
if ((variation & mask) == mask)
{
sum += list[bit - 1];
}
mask <<= 1;
}
if (sum > Lower && sum < Upper)
{
return true;
}
}
return false;
}
Cela pourrait être mieux résolu par un réseau de flux
Merci Nominsim Mais, un algorithme plus simple existe-t-il?
Pour une force brute, vous aurez besoin de toutes les permutations résumées, dont il y aura n! Cela deviendra cher rapidement sans quelque chose d'un peu plus chic que je pense.
@Adammills Brute Force est N * 2 ^ N, pas n!