Merci beaucoup pour votre commentaire. Je cherche effectivement à être le plus concret possible dans mes explications et ce genre d'algorithme est très intéressant mais pas forcément accessible. Je suis content que le message soit passé.
Je suis actuellement entrain de me préparer au concours de programmation Prologin, et je m'interresse aux 21 problèmes NP Complets de Karp pour m'améliorer. Cette vidéo m'a beaucoup aidé, surtout qu'il fallait utiliser un Algorithme du sac à dos pour un des problèmes. Grâce à vous, je suis devenu un peu meilleur ^^ !
Super, j'adore ce genre de problème qui peut être solutionné de différentes manières, chacune ayant ses avantage et ses inconvénient. Je découvre également grâce à vous le concours Prologin que je ne connaissais pas :D
@@algomius J'essaie actuellement d'adapter votre solution dynamique à mon cas d'étude qui contient des float ce qui malheureusement pose problème a cette ligne : matrice[i][w] = max(actions[i-1][2] + matrice[i-1][w-actions[i-1][1]], matrice[i-1][w])
Ce qui pose en fait problème est cette instruction : matrice[i-1][w-elements[i-1][1]]. Si vous avez des poids réels, w-elements[i-1][1] ne sera pas entier, or cette valeur est utilisée comme indice de tableau et se doit d'être entier. La façon la plus simple est de convertir vos poids. Par exemple, 3,5 kg devient 3500 g. Naturellement pour que cela fonctionne il faut mettre la capacité du sac à dos dans la même unité. Si vous transformez tout en grammes, vous retombez sur des entiers, sinon, passez en mg :D
@@algomius Merci de l'astuce je n'y avais pas pensé ! Dans mon cas il s'agit d'investissement en bourse avec des coûts d'actions en € float et des profits en € et float également. Je vais essayer de passer tout ça en centimes
Merci pour ces explications sympas. Juste une remarque : dans le code, il n'est pas nécessaire de réinitialiser la liste des éléments à chaque fois, puisque les fonctions ne la modifient pas.
Bonjour. stp si on a plusieurs sac a dos et on veut maximiser la valeur des objets comment peut-on faire ? un projet de recherche opérationnelle vise à utiliser le problème du sac à dos pour l'optimisation du chargement de camions pour la livraison de marchandises. Le projet consiste à développer un modèle d'optimisation pour maximiser la valeur des marchandises transportées tout en respectant la capacité de charge maximale de chaque camion.
Je réfléchis à votre question mais je dois dire que je ne sais pas. Est-ce que décomposer le programme en chargeant 1 à 1 les camions va t'il donner au final la meilleure solution ? Pas sûr. Je crois que vous cherchez à résoudre un problème qui s'appelle MKP (multiple knapsack problem). Je n'ai pas trop regardé mais vous avez une explication ici : towardsdatascience.com/the-binary-multidimensional-knapsack-problem-mkp-2559745f5fde . La résolution semble s'appuyer sur un modèle implémenté dans une bibliothèque et ne semble aps vraiment expliquer la résolution.
J'ai ajouté des timers et l'algo en programmation dynamique est 1000 fois plus lent que l'algo glouton. Cela peut être lié à l'utilisation de listes imbriquées ?
Non, c'est tout a fait normal. Un algorithme glouton s'appuie sur une règle naîve pour trouver une bonne solution. Il est le plus rapide mais la solution donnée n'est pas la solution optimale. En face, la programmation dynamique est plus lente mais garantie que la solution trouvée est optimale. La programmation dynamique est la solution la plus rapide qui donne la solution optimale, plus rapide que la force brute.
@@algomius En théorie oui, mais en pratique cet algo en programmation dynamique est 1000 fois plus LENT que celui en force brute quand on mesure les temps d'excution effectifs par python, d'où mon étonnement.
Bonjour, merci pour votre vidéo. Mais je n'arrive pas à comprendre quelque chose, pour la version en force brute. Pourquoi par exemple, 'val1' nous donne la valeur d'un objet et 'lstVal1' nous donne la liste de cet objet. Comment cela fonctionne, s'il vous plaît ?
Oui, je comprends, ce n'est pas toujours évident de s'y retrouver, je suppose que vous parlez de la ligne suivante : val1, lstVal1 = sacADos_force_brute(capacite, elements[1:], elements_selection) Python permet aux fonctions de renvoyer plusieurs résultats séparés par des virgules, val1 reçoit donc le premier retour, lstVal1 le second. Il faut donc s'intéresser aux retours de la fonction sacADos_force_brute. Le retour de cette fonction se trouve un peu plus bas : return sum([i[2] for i in elements_selection]), elements_selection Le premier élément renvoyé est sum([i[2] for i in elements_selection]), c'est la somme de tous les éléments de la liste. Il s'agit là d'une somme d'entiers, donc la somme est de type entier également. Le second élément renvoyé est elements_selection. Il s'agit là de la liste des éléments sélectionnés. Donc la fonction sacADos_force_brute renvoie un entier, suivi d'une liste. C'est pour cela que quand j'écris : val1, lstVal1 = sacADos_force_brute(capacite, elements[1:], elements_selection) val1 est un entier et lstVal1 est une liste. J'espère avoir été clair.
Bonjour, merci pour cette vidéo. Petite question par contre je n'ai pas bien saisi pourquoi on retourne au final matrice[-1][-1] , et non pas matrice[n][w] ? Merci d'avance pour vos lumières
Merci pour votre retour. matrice[-1][-1] signifie simplement que je retourne l'élément qui se trouve à la dernière ligne et la dernière colonne, donc le dernier élément de la matrice. C'est une notation possible en Python. - Tab[-1] retourne le dernier élément du tableau - Tab[-2] retourne l'avant dernier élément du tableau ...
Bonjour Algomius! Merci pour cette vidéo. J'ai repris ton code et j'ai rajouté des print (que j'ai mis en uppercase ici) pour essayer de comprendre comment fonctionnait ton algorithme C'est peut-être la fonction récursive qui me perturbe mais en gros je ne comprends pas dans quel ordre le code est lu. Pour moi, quand on appelle cette fonction on devrait avoir un premier print 'start' puis 'elements', puis quand on arrive à la ligne avec la variable val1, lstVal1, comme on l'appelle à nouveau, un deuxième print 'start' puis 'elements' Or dans ma console, j'ai 3 print start à la suite avant même d'avoir mon print pour val1, lstVal1. Pourquoi? Par ailleurs, val est défini comme étant le premier élément de l'argument elements, et donc pour moi c'est ('Montre à gousset', 2, 6). Or dans mon print de val, j'obtiens ('Portrait de tata Germaine', 4, 12) Pourrais tu m'expliquer dans quel ordre le code est lu? LES PRINTS QUE J'AI RAJOUTE: def sacADos_force_brute(capacite, elements, elements_selection=[]): PRINT('START')
Bonjour, C'est une bonne idée de tracer la fonction comme tu l'as fait. Ce que tu peux ajouter pour y voir encore plus clair, c'est afficher les arguments d'appel de la fonction directement dans le print start. Cela te permettra de voir directement avec quels arguments est appelée la fonction. Pour expliquer cette fonction : On parcours les éléments disponible et pour chacun on se pose la question, est-ce que je le prends ou je ne le prends pas ? Le premier appel considère qu'on ne le prend pas, le second vérifie si on est toujours bon du point de vu de la capacité et si oui, on considère que on le prend. Mais a partir du moment où tu appelles la fonction, elle va se dérouler jusqu'au bout. Pour mieux comprendre tu peux représenter ca sous forme d'arbre. Tu pars de la racine, pour chaque objet tu prends ou tu prends pas, ensuite, pour chacun de ces deux cas, tu prends ou tu ne prends pas le second objet et ainsi de suite. L'algorithme va juste suivre la première branche jusqu'au bout puis il va revenir.
Bonjour, vous devez toujours travailler avec des entiers, donc le plus souvent, on change d'unité. On passe des kg aux grammes pour faire disparaitre la virgule. Si ce n'est pas possible, cela devient malheureusement une limite de cet algorithme.
Merci pour votre commentaire. En regardant l'algorithme de plus près, je ne vois pas pourquoi les valeurs des objets ne pourraient pas être définies en nombres décimaux. Le problème va venir du poids des objets. Lui, est utilisé dans les calculs d'indice et un indice de tableau est forcément entier. Une façon de résoudre le problème serait peut être de multiplier par 10 tous les poids tant qu'un des poids possède une partie décimale (tant que p % 10 0) et de multiplier également la capacité par 10 à chaque fois. Finalement c'est comme passer un objet de 1,5 kg en 1500g. Attention toutefois, si vous avez des nombres avec un grand nombre de chiffres après la virgule, vous risquez de boucler un long moment.
L'algo en programmation dynamique est 1000 fois plus LENT que celui en force brute quand on mesure les temps d'excution effectifs par python, d'où mon étonnement. (Dans mon message précédent j'ai confondu les termes glouton et force brute).
Est ce que ca ne viendrait pas du fait que vous travaillez avec un problème très simple ? (3 objets). Les complexités algorithmiques sont vraies pour un grand nombre d'éléments mais si le problème est très simple, la force brute peut être plus rapide.
Je tombe petit à petit amoureux de vos vidéos... Ayant pris la spécialité nsi en terminal votre contenu m'aide ENORMEMENT. Alors un GRAND merci
Je suis très contant que les vidéos vous aident. Je ne connais pas bien le programme de NSI mais je vais me renseigner :D
Merci beaucoup. Vous offrez une des meilleures explications de ce sujet que l’on peut trouver sur cette plateforme. Merci.
Merci beaucoup pour votre commentaire. Je cherche effectivement à être le plus concret possible dans mes explications et ce genre d'algorithme est très intéressant mais pas forcément accessible. Je suis content que le message soit passé.
Merci pour vos explications, c'était limpide ! Cela m'a énormément aidé, merci beaucoup !
Merci pour votre retour. L'algorithme du sac à dos est vraiment intéressant, il s'exprime simplement mais n'est pas si facile à résoudre.
Je suis actuellement entrain de me préparer au concours de programmation Prologin, et je m'interresse aux 21 problèmes NP Complets de Karp pour m'améliorer. Cette vidéo m'a beaucoup aidé, surtout qu'il fallait utiliser un Algorithme du sac à dos pour un des problèmes. Grâce à vous, je suis devenu un peu meilleur ^^ !
Super, j'adore ce genre de problème qui peut être solutionné de différentes manières, chacune ayant ses avantage et ses inconvénient. Je découvre également grâce à vous le concours Prologin que je ne connaissais pas :D
Très intéressant et très claire votre explication ! Ca m'enlève une épine du pied. Merci beaucoup
Le sac à dos est vraiment un algorithme intéressant pour comprendre les notions d'optimisation. je suis content que cette vidéo ait pu vous aider.
@@algomius J'essaie actuellement d'adapter votre solution dynamique à mon cas d'étude qui contient des float ce qui malheureusement pose problème a cette ligne : matrice[i][w] = max(actions[i-1][2] + matrice[i-1][w-actions[i-1][1]], matrice[i-1][w])
Ce qui pose en fait problème est cette instruction : matrice[i-1][w-elements[i-1][1]]. Si vous avez des poids réels, w-elements[i-1][1] ne sera pas entier, or cette valeur est utilisée comme indice de tableau et se doit d'être entier. La façon la plus simple est de convertir vos poids. Par exemple, 3,5 kg devient 3500 g. Naturellement pour que cela fonctionne il faut mettre la capacité du sac à dos dans la même unité. Si vous transformez tout en grammes, vous retombez sur des entiers, sinon, passez en mg :D
@@algomius Merci de l'astuce je n'y avais pas pensé ! Dans mon cas il s'agit d'investissement en bourse avec des coûts d'actions en € float et des profits en € et float également. Je vais essayer de passer tout ça en centimes
Enfin je comprends le principe de l’algorithme dynamique pour la résolution du problème knapsack! ‘Merci’ for x in range(100000) 😁
Super, c'est un problème effectivement très simple à énoncer mais pas si facile à résoudre.
Merci pour ces explications sympas. Juste une remarque : dans le code, il n'est pas nécessaire de réinitialiser la liste des éléments à chaque fois, puisque les fonctions ne la modifient pas.
Merci pour le retour, je suis toujours content que des gens cherchent à comprendre ce genre d'algo.
Bonjour. stp si on a plusieurs sac a dos et on veut maximiser la valeur des objets comment peut-on faire ? un projet de recherche opérationnelle vise à utiliser le problème du sac à dos
pour l'optimisation du chargement de camions pour la livraison de
marchandises. Le projet consiste à développer un modèle d'optimisation pour
maximiser la valeur des marchandises transportées tout en respectant la
capacité de charge maximale de chaque camion.
Je réfléchis à votre question mais je dois dire que je ne sais pas. Est-ce que décomposer le programme en chargeant 1 à 1 les camions va t'il donner au final la meilleure solution ? Pas sûr. Je crois que vous cherchez à résoudre un problème qui s'appelle MKP (multiple knapsack problem). Je n'ai pas trop regardé mais vous avez une explication ici : towardsdatascience.com/the-binary-multidimensional-knapsack-problem-mkp-2559745f5fde . La résolution semble s'appuyer sur un modèle implémenté dans une bibliothèque et ne semble aps vraiment expliquer la résolution.
J'ai ajouté des timers et l'algo en programmation dynamique est 1000 fois plus lent que l'algo glouton. Cela peut être lié à l'utilisation de listes imbriquées ?
Non, c'est tout a fait normal. Un algorithme glouton s'appuie sur une règle naîve pour trouver une bonne solution. Il est le plus rapide mais la solution donnée n'est pas la solution optimale. En face, la programmation dynamique est plus lente mais garantie que la solution trouvée est optimale. La programmation dynamique est la solution la plus rapide qui donne la solution optimale, plus rapide que la force brute.
@@algomius En théorie oui, mais en pratique cet algo en programmation dynamique est 1000 fois plus LENT que celui en force brute quand on mesure les temps d'excution effectifs par python, d'où mon étonnement.
Bonjour, merci pour votre vidéo. Mais je n'arrive pas à comprendre quelque chose, pour la version en force brute. Pourquoi par exemple, 'val1' nous donne la valeur d'un objet et 'lstVal1' nous donne la liste de cet objet. Comment cela fonctionne, s'il vous plaît ?
Oui, je comprends, ce n'est pas toujours évident de s'y retrouver, je suppose que vous parlez de la ligne suivante :
val1, lstVal1 = sacADos_force_brute(capacite, elements[1:], elements_selection)
Python permet aux fonctions de renvoyer plusieurs résultats séparés par des virgules, val1 reçoit donc le premier retour, lstVal1 le second. Il faut donc s'intéresser aux retours de la fonction sacADos_force_brute. Le retour de cette fonction se trouve un peu plus bas :
return sum([i[2] for i in elements_selection]), elements_selection
Le premier élément renvoyé est sum([i[2] for i in elements_selection]), c'est la somme de tous les éléments de la liste. Il s'agit là d'une somme d'entiers, donc la somme est de type entier également.
Le second élément renvoyé est elements_selection. Il s'agit là de la liste des éléments sélectionnés.
Donc la fonction sacADos_force_brute renvoie un entier, suivi d'une liste. C'est pour cela que quand j'écris :
val1, lstVal1 = sacADos_force_brute(capacite, elements[1:], elements_selection)
val1 est un entier et lstVal1 est une liste.
J'espère avoir été clair.
@@algomius merci de votre réponse. Oui c'est très clair.🙂
Bonjour, merci pour cette vidéo. Petite question par contre je n'ai pas bien saisi pourquoi on retourne au final matrice[-1][-1] , et non pas matrice[n][w] ? Merci d'avance pour vos lumières
Merci pour votre retour. matrice[-1][-1] signifie simplement que je retourne l'élément qui se trouve à la dernière ligne et la dernière colonne, donc le dernier élément de la matrice. C'est une notation possible en Python.
- Tab[-1] retourne le dernier élément du tableau
- Tab[-2] retourne l'avant dernier élément du tableau
...
Bonjour, j’aimerais savoir si il faut d’abord trier les éléments par leur poids ou non ?
Bonjour, dans la solution gloutonne il faut trier les objets, dans les 2 autres non
Bonjour Algomius!
Merci pour cette vidéo. J'ai repris ton code et j'ai rajouté des print
(que j'ai mis en uppercase ici) pour essayer de comprendre comment fonctionnait ton algorithme
C'est peut-être la fonction récursive qui me perturbe mais en gros je ne comprends pas dans quel ordre le code est lu.
Pour moi, quand on appelle cette fonction on devrait avoir un premier print 'start' puis 'elements',
puis quand on arrive à la ligne avec la variable val1, lstVal1, comme on l'appelle à nouveau, un deuxième print 'start' puis 'elements'
Or dans ma console, j'ai 3 print start à la suite avant même d'avoir mon print pour val1, lstVal1.
Pourquoi?
Par ailleurs, val est défini comme étant le premier élément de l'argument elements, et donc pour moi
c'est ('Montre à gousset', 2, 6). Or dans mon print de val, j'obtiens ('Portrait de tata Germaine', 4, 12)
Pourrais tu m'expliquer dans quel ordre le code est lu?
LES PRINTS QUE J'AI RAJOUTE:
def sacADos_force_brute(capacite, elements, elements_selection=[]):
PRINT('START')
if elements:
PRINT('ELEMENTS', ELEMENTS)
val1, lstVal1 = sacADos_force_brute(capacite, elements[1:], elements_selection)
val = elements[0]
PRINT('VAL1, LSTVAL1, VAL', VAL1, LSTVAL1, VAL)
if val[1]
Bonjour, C'est une bonne idée de tracer la fonction comme tu l'as fait. Ce que tu peux ajouter pour y voir encore plus clair, c'est afficher les arguments d'appel de la fonction directement dans le print start. Cela te permettra de voir directement avec quels arguments est appelée la fonction. Pour expliquer cette fonction : On parcours les éléments disponible et pour chacun on se pose la question, est-ce que je le prends ou je ne le prends pas ? Le premier appel considère qu'on ne le prend pas, le second vérifie si on est toujours bon du point de vu de la capacité et si oui, on considère que on le prend. Mais a partir du moment où tu appelles la fonction, elle va se dérouler jusqu'au bout.
Pour mieux comprendre tu peux représenter ca sous forme d'arbre. Tu pars de la racine, pour chaque objet tu prends ou tu prends pas, ensuite, pour chacun de ces deux cas, tu prends ou tu ne prends pas le second objet et ainsi de suite. L'algorithme va juste suivre la première branche jusqu'au bout puis il va revenir.
Comment peut on adapter l'algorithme dynamique pour un cas ou la valeur et le poids des objets sont non entier?
Bonjour, vous devez toujours travailler avec des entiers, donc le plus souvent, on change d'unité. On passe des kg aux grammes pour faire disparaitre la virgule. Si ce n'est pas possible, cela devient malheureusement une limite de cet algorithme.
@@algomius Le problème c'est que changer d'unité multiplie la capacité par 1000 et la complexité aussi, ce qui réduit d'autant la vitesse d'exécution
Merci pour cette très bonne explication. Mais comment cela se passerait si les éléments (poids, valeurs) étaient des floats ?
Merci pour votre commentaire. En regardant l'algorithme de plus près, je ne vois pas pourquoi les valeurs des objets ne pourraient pas être définies en nombres décimaux. Le problème va venir du poids des objets. Lui, est utilisé dans les calculs d'indice et un indice de tableau est forcément entier. Une façon de résoudre le problème serait peut être de multiplier par 10 tous les poids tant qu'un des poids possède une partie décimale (tant que p % 10 0) et de multiplier également la capacité par 10 à chaque fois. Finalement c'est comme passer un objet de 1,5 kg en 1500g.
Attention toutefois, si vous avez des nombres avec un grand nombre de chiffres après la virgule, vous risquez de boucler un long moment.
Pouvez vous m'envoyer le code source j'ai vraiment besoin de ce code
Le code est disponible dans la description
Bien mais le son uniquement a gauche est rébarbatif.
Merci pour votre retour. Effectivement les premières vidéos sont en mono, c'est un soucis que j'ai corrigé par la suite.
L'algo en programmation dynamique est 1000 fois plus LENT que celui en force brute quand on mesure les temps d'excution effectifs par python, d'où mon étonnement. (Dans mon message précédent j'ai confondu les termes glouton et force brute).
Est ce que ca ne viendrait pas du fait que vous travaillez avec un problème très simple ? (3 objets). Les complexités algorithmiques sont vraies pour un grand nombre d'éléments mais si le problème est très simple, la force brute peut être plus rapide.
Avec 100 objects effectivement l'algo dynamique est 77 fois plus rapide !
Algo force 904.714480 seconds
Algo dynamique 11.607185 seconds