Il y a un dernier truc sur lequel je bloque encore un peu. Cette fonction récursive sort toutes les possibilités qui peuvent rentrer dans le sac, elle compare les valeurs avec val1 et val2. Mais je ne comprends pas comment elle compare toutes les valeurs entre elles. Je vois qu'elle compare la valeur actuelle avec la valeur précédente, mais en faisant un print de sortie, je ne vois pas comment elle compare toutes les combinaisons entre elles au final.
En fait, la première fois qu'elle s'appelle elle même (à la ligne 3), elle ne fait rien, c'est ça (car le premier print du return donne '0 []')?
elle compare le poids du 1er objet à la capacité fournie. la magie c'est la récursivité, on appelle à nouveau la fonction, avec la nouvelle capacité et avec la liste des éléments sans le 1er; donc de manière récursive on parcourt la liste des éléments.
Mais par exemple(je me sers du degub pour parcourir le code et essayer de mieux le comprendre) sur la liste de 3 éléments, il va d'abord supprimer le premier, on boucle, il supprime le deuxième, on boucle, puis il supprime le dernier.
Et donc la on va dans le else pour en sortir '0[]'. Jusqu'a la, je comprends.
Mais pourquoi ensuite on repart avec le dernier élément(Portait) dans la liste ? Je ne comprends pas, puisque juste avant, on avait la liste vide.
on ne supprime pas, on fait appel (Appel1) à la même fonction mais en partant de l'élément suivant (ligne 3), qui va à son tour s'appeler (Appel2) en partant de l'élément suivant (qui sera donc ici le dernier), on va encore appeler (Appel3) la fonction, comme elements sera vide, on retournera la somme du poids (ici 0,[]).
On poursuit ensuite le programme, donc ligne 4, si le poids du denier element de la liste (qui est à ce moment element[0]) est inférieur à la capacité, on s'appelle en passant la nouvelle capacité, le tableau des éléments (sans l'élément courant) et un elements_selection correspondant à l'élément courant.
Comme dans cet appel, elements est vide, on va dans le else, donc on va retourner la somme des éléments_selection, donc le poids de l'objet, la liste elements_selection (soit 6,[('Portrait',6,20)]); val1 valant 0 et val2 valant 6, on retourne val2 et lstVal2, soit 6,[('Portrait',6,20)]
Ces valeurs correspondent (si je ne me suis pas perdu) à val1,lstVal1 du second appel (donc Appel2) de la ligne 3 et on poursuit le programme pour cet appel
Popopoooo ...ok! Donc ça y est je crois que je vois!
Donc au premier appel, 'element[1:]'vaut le second objet, donc ('Boule', 3, 1), on le boucle une deuxième fois, et donc 'element[1:]' vaut ('Portrait', 6, 20), on le boucle une troisième fois, et donc 'element[1:]' vaut ([]), et on passe au else....mais en fait 'element[0]' vaut bien ('Portrait', 6, 20) et pas ([]), c'est bien ça ? Et oui comme tu dis, 'element[1:] ne supprime pas, il parcourt, c'est tout. donc 'element[0]' vaut bien le dernier élément.
C'est ça qui me perturbait.
Merci beaucoup de t'être embêté à écrire tout ça, c'est très gentil, merci!
Bon sang, en tant que débutant, ce n'est pas du tout évident, le récursif et l'algo en force brute en même temps...
Donc au premier appel, 'element[1:]'vaut le second objet, donc ('Boule', 3, 1), on le boucle une deuxième fois, et donc 'element[1:]' vaut ('Portrait', 6, 20), on le boucle une troisième fois, et donc 'element[1:]' vaut ([]), et on passe au else....mais en fait 'element[0]' vaut bien ('Portrait', 6, 20) et pas ([]), c'est bien ça ?
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
et il n'y a pas de boucles ^^, on appelle 3 fois la ligne 3 à la inception (le film): on plonge dans un rêve (n°1) dans lequel on plonge dans un rêve (n°2 qui est le même que le n°1 ici) dans lequel on plonge dans un rêve (n°3); quand on sort du n°3, on est dans le n°2 et on peut poursuivre ce rêve; ensuite on sort du rêve n°2 et on est toujours dans le n°1, il faut sortir du n°1 pour refaire surface (et rien n'empêche de repartir dans un autre rêve quand on revient au rêve précédent)
Si tu veux voir pourquoi ça s'appelle "force brute", je te donne un vieux problème que je devais résoudre. On a un ensemble de 1000 bandes magnétiques remplies entre 1% et 100% Trouver le plus grand nombre de bandes qu'on peut fusionner pour en générer une (ne dépassant pas 100%). J'ai utilisé une méthode approximative car ma machine n'avait pas de pile, donc pas de récursivité efficace. Il suffit de donner 1 comme valeur à chaque bande: from random import randint pool = [('UM'+str(i+1+10000)[-4:], randint(1, 100), 1) for i in range(1000)] Et on appelle la fonction avec une capacité de 100 Tu verras que c'est relativement long à exécuter.
- Edité par PierrotLeFou 30 mars 2022 à 18:59:07
Le Tout est souvent plus grand que la somme de ses parties.
Explication sur le code de force brute
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Le Tout est souvent plus grand que la somme de ses parties.