Discussion :

[FloBLk]

Bonjour à tous,

Voilà mon problème :

J'aimerai créer une fonction permettant de retourner une list<int> correspondant aux termes d'une addition possible pour un nombre donné à coté.
Un exemple pour être plus clair :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
 
List<int> maListe; // est une liste d'entiers qui est possible à additionner, elle est composée de 1, 5, 10, 20, 30
int maSomme = 26; // 26 est la somme à trouver
 
// la fonction à coder
public List<int> ReturnList(List<int> liste, int total)
{
// J'aimerai donc que ce code traite ma liste de nombres passée en paramètre et le total à trouver, afin de me retourner dans notre exemple une List<int> composé de 20, 6, et 1 qui match avec une addition possible.
// Une idée ?
}

Je pense que des boucles for() imbriqués avec la gestion de List<> peut me sortir d'affaire mais j'ai beau retourner tout ça dans tous les sens, je pense atteindre mes limites...
Je suis donc à l'écoute de vos conseils

Merci d'avance

[PixelJuice]

Petite question (si j'ai bien compris ton problème) :

Les nombres de la liste données , tu veux qu'ils soient réutilisables ou non ?

Si c'est réutilisable :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        private List<int> ReturnList(List<int> liste, int total)
        {
            int totalATrouver = 0;
            List<int> listeAEnvoyer = new List<int>();
            liste.Reverse(); // On commence par les nombres les plus grand afin d'affiner l'addition tout au long
 
            while (totalATrouver != total)
            {
                for (int i = 0; i < liste.Count; i++)
                {
                    if (totalATrouver + liste[i] <= total)
                    {
                        totalATrouver += liste[i];
                        listeAEnvoyer.Add(liste[i]);
                    }
                }
            }
 
            return listeAEnvoyer;
        }

Sinon :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        private List<int> ReturnList(List<int> liste, int total)
        {
            int totalATrouver = 0;
            List<int> listeAEnvoyer = new List<int>();
            liste.Reverse();
 
            while (totalATrouver != total)
            {
                for (int i = 0; i < liste.Count; i++)
                {
                    if (totalATrouver + liste[i] <= total && !listeAEnvoyer.Contains(liste[i]))
                    {
                        totalATrouver += liste[i];
                        listeAEnvoyer.Add(liste[i]);
                    }
                }
            }
 
            return listeAEnvoyer;
        }

Si ça ne corresponds pas a ton problème , j'en suis désolé mais ça devrait te mettre sur une piste.

[Pragmateek]

C'est plus un problème d'algorithmie, et ça tombe bien le forum Développez a une section dédiée.

J'ai demandé à un modo de déplacer ce thread...

[FloBLk]

Merci pour vos réponse,

En effet PixelJuice, j'avais pensé à m’orienter vers un algo de la sorte mais ça ne fonctionne pas dans mon cas (des nombres se trouves dans mon tableau mais ne sont pas forcément utiles au calcul).

Par exemple je peux avoir le tableau :
6, 12, 19, 29, 45, 48, 90, 162 avec pour recherche 284 (la bonne solution serait de me retourner un tableau : 162, 48, 45, 29)
hors avec cette algo je vais bloquer sur un tableau du style : 162, 90, 29... et la ça va tourner en boucle car 162 + 90 + 29 = 281 soit < à 284 et aucune autre combinaison ne pourra me faire tomber sur 284

vous voyez mon problème :s ?

J'ai en effet trouver d'autres sujets sur la partie Algo du forum qui se rapprochent de mon problème mais je n'arrive pas à faire coller une solution adéquate, alors j'aurai espéré trouver une solution ici.

Merci encore

[DonQuiche]

Je vais présumer que tu ne souhaites utiliser chaque nombre qu'une fois (du moins pas plus de fois que le nombre d'occurences dans la liste de départ) :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
List<int> ReturnList(List<int> liste, int total)
{
    liste.Sort();
    liste.Reverse();
 
    var valeurs = liste.ToArray();
    if (RetirerValeursJusquAuRésultat(valeurs, 0, total))
    {
        return ListerValeursRetirées(liste, valeurs).ToList();
    }
 
    throw new ArgumentException("Pas de combinaison.");
}
 
bool RetirerValeursJusquAuRésultat(int[] valeurs, int début, int total)
{
    if (total == 0) return true;
 
    for (int i = début; i < valeurs.Length; ++i)
    {
        var valeur = valeurs[i];
        if (valeur > total) continue;
 
        valeurs[i] = 0;
        if (RetirerValeursJusquAuRésultat(valeurs, i + 1, total - valeur)) return true;
        valeurs[i] = valeur;
    }
 
    return false;
}
 
IEnumerable<int> ListerValeursRetirées(List<int> liste, int[] valeurs)
{
    for (int i = 0; i < valeurs.Length; ++i)
    {
        if (valeurs[i] == 0) yield return liste[i];
    }
}

PS : les perfs peuvent être améliorées en affinant "début" par recherche dichotomique à chaque étape.

[FloBLk]

Merci de vos réponses , je me penche sur ces codes.