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.

[ToTo13]

Tu peux faire une recherche exhaustive grâce à une récursivité, mais il faut que tu affines un peu la recherche :
- tu ne gardes la solution que si elle est égale à la somme souhaitée.
- tu écourtes la recherche si en route tu dépasses déjà la somme recherchée
- tu ne réutilises aucun nombre déjà utilisé.

[FloBLk]

Merci de tes conseils Toto, très bonne remarque.
Je prend note :-)

[Flodelarab]

Bonjour,

de mon point de vue, tu essaies de résoudre le problème du sac à dos qui n'a pas de solution théorique.
Cette incapacité assure la sécurité de pas mal de systèmes cryptographiques.

Le fait de payer le pain dans la boulangerie est facile car la monnaie est une suite hypergéométrique 1 2 5 10 20 50 100 200 500 ...
Si ce n'était pas le cas, on se prendrait la tête comme toi sur ton prog c++.

Il faut donc faire tous les cas possibles. Avec la montée en charge, ton prog va s'écrouler.

[disedorgue]

Bonjour,

Il est vrai que c'est un problème difficile, mais tu peux sensiblement réduire tes calculs en sommant tous les nombre de ton tableau, puis en soustrayant le résultat par le nombre recherché et tu recherche la liste des nombres pouvant additionner le plus petit des 2 et à la fin sois tu conserve les nombres trouvé soit tu les élimine.
Un exemple sera plus claire (en reprenant ton exemple avec 284):
6+12+19+29+45+48+90+162 = 411
411-284 = 127
Donc ici, on recherche pour 127, et non 284
90+19+12+6 = 127
On élimine donc ces nombres, car on c'est que les autres restants (29,45,48,162) feront en les additionnant 284.

Tu pourrais aussi calculer en // pour les 2 nombres (284 et 127 dans l'exemple) et arrêter dés que l'un des 2 calculs retourne un résultat...