Une vidéo qui m'a bien rendu service ! En codant l'algorithme en Kotlin je n'obtenais pas le résultat attendu dans la matrice P car le premier encadré dans l'algorithme complet sur la vidéo (vers 12:12) est mal positionné. La ligne qui le suit (renseigner f[C,i]) doit précéder les opérations réalisées dans l'encadré. Et ainsi ça fonctionne impeccablement. Merci !
Bonjour Win Ecran Oui je crois que tu as raison. Une erreur d'indice s'est glissée dedans car j'ai du remettre en page l'algorithme pour gagner de la place et pour clarifier. J'ai mis une petite correction en fin de description. Il me semble que tu dois régler le problème (sans inverser les lignes) en remplaçant f[C,i] par f[C,i-1] dans le deuxième SI. Dis moi si ça marche ! Merci encore !
Super vidéo ! Les schémas rendent toutes les explications ludiques et claires. Cependant j'aimerai ajouter quelque chose. Il me semble que pour trouver la solution à partir de la matrice des valeurs max de sac, il n'est pas nécessaire d'avoir une seconde matrice de prédécésseurs (qui double l'espace nécessaire au calcul). Une autre méthode permet de trouver une solution optimale. La voici : -On part de la dernière case notons la i,j, qui est de valeur optimale. Pour chaque colonne. -Si la case i,j-1 a la même valeur que la case actuelle. Alors on a pas pris l'objet j et on passe sur la case i,j-1. Cela se conçoit par le fait que, rajouter le dernier objet dans l'équation n'a pas changé la valeur maximale du sac, donc ne pas le prendre revient au même. Même si il est possible que l'arrivée du dernier objet ait changé l'organisation du sac (remplacements d'un ou plusieurs objet par le dernier). On a tout de même une solution optimale en ne le prenant pas. -Sinon, on a pris l'objet j, donc on va à la case i-wj,j-1. Cela se conçoit une fois de plus par le fait que prendre l'objet j dans l'équation a changé la valeur du sac, donc on l'a forcément mis dans le sac. Si ce n'est pas le cas c'est que la solution précédente aurait pu être meilleure, ce qui contredit hypothèse d'optimalité des cases de la matrice. Un object de poids 0 ne change rien à cela puisqu'on irait alors sur la case i-0,j-1 en ayant bel et bien pris cet objet. On repète cette opération jusqu'à arriver en 0,0 On pourrait argumenter sur le fait que cet algorithme ne suit pas forcément les choix fait durant le remplissage du tableau, ce qui est vrai. Mais : -La solution est optimale donc on a ce qu'on cherche. -L'algorithme de remplissage fait déjà des choix arbitraires en cas d'égalité des deux solutions. Seules cas ou la méthode de la seconde matrice et celle ci dessus peuvent diverger. Donc on a pas moins d'information dans un cas que dans l'autre.
Bonjour Stricorteur, Merci de ton retour et de ta question, ça fait plaisir :) Je suis tout à fait d’accord avec toi ! J’ajoute deux choses: - Du point de vue de la complexité au pire cas, la consommation en espace (l’allocation mémoire pour la table) est en O(nW). Un x2 ("fois deux") ne change rien de ce point de vue. En pratique en revanche, tu as raison cela peut faire une grosse différence. (je n'avais pas bien compris ce que tu disais, j'essaie donc de clarifier pour éviter la confusion :)) - En faisant ce que tu proposes, tu pars d'une case optimale finale et tu re-testes les deux choix à chaque fois en remontant de colonnes en colonnes (tu re-calcules le max n fois) mais cela reste bien en O(n). Cela ne coûte pas plus cher que de parcourir la table des prédécesseurs p à la fin pour sortir une solution optimale i.e O(n). En revanche plus l’algorithme va être couteux en temps (si au lieu de deux cases à évaluer à chaque fois, tu en as n par exemple un max à faire sur n case) alors cela va devenir un plus coûteux. Il peut du coup devenir intéressant (dans d'autres programmes dynamique) de stocker le résultat dans p pour éviter de refaire ces calculs « en arrière » à la fin. Donc globalement cet algorithme (ou ta proposition) est en O(nW) en espace et aussi en temps. Et dans le cas précis du sac à dos, ta proposition pourrait bien être plus rapide en pratique car allouer de la mémoire prends aussi du temps :) Par contre, il y a des cas ou on peut réduire la complexité spatiale au prix d'une petite augmentation de la complexité temporelle. Si cela t'intéresse (va d'abord au bout de ton cours de prog. dyn), tu peux aller regarder l'exercice 6.24 (Time and space complexity of dynamic programming) de ce livre: people.eecs.berkeley.edu/~vazirani/algorithms/chap6.pdf Enfin Il aussi existe d'autre façon d'implémenter la table pour éviter d'allouer toute cette mémoire et améliorer en pratique. Cette grosse matrice est souvent très creuse en réalité. Nous avons fait ici vraiment la base. J'espère faire quelques vidéos pour aller plus loin et détailler tout ça. J'espère que j'ai bien compris ce que tu disais ! Bonne journée Hadrien
@@rechercheoperationnelle8907 Merci pour ces explications, cependant il me semble que dans ma stratégie, remonter la table se passe également en O(n). La colonne sur laquelle on travail décroit strictement à chaque itération. On a donc au plus n vérification et affectations. Voici un exemple d'exécution sur l'exemple de la vidéo à 10:07 : On commence à la case (10,5). case(10,5) = case(10,4) ? OUI -> on part sur la case (10,4) et l'objet 5 n'est pas pris. On est sur (10,4). case(10,4) = case(10,3) ? NON -> on passe sur la case(10-w4,3) soit case(6,3) et l'objet 4 est pris. On est sur (6,3). case(6,3) = case(6,2) ? NON -> on passe sur la case(6-w3,2) soit case(2,2) et l'objet 3 est pris. On est sur (2,2). case(2,2) = case(2,1) ? OUI -> on passe sur la case(2,1) et 2 n'est pas pris. On est sur la case(2,1). case(2,1) = case(2,0) ? NON -> on passe sur la case(2-w1,0) soit case(0,0) et l'objet 1 est pris. L'algorithme est terminé. On a donc pris les objets 1,3,4. Ce qui est bien notre solution optimale. Le parcours s'est fait en 5 étape. On aurait donc O(nW + n) = O(nW) en temps. N'hésitez pas à me reprendre si une faille se trouve dans mon raisonnement. J'essaierai d'aller voir l'exercice du livre si je trouve le temps.
@@bertrandbaudeur5536 Ah ok je vois mieux, tout à fait ! Effectivement si tu fais ça c'est en O(n), pas de soucis ! Donc pour faire la différence, imagine que tu as n cases à vérifier avant et pas juste 2, ta stratégie pour "détricoter" est dans ce cas en O(n^2) et va dans ce cas couter un peu plus cher. Je voulais juste faire cette différence pour dire que si tu n'a pas de problème de mémoire, stocker le meilleur choix peut t'éviter ce recalcul. Ce qui est "particulier" ici c'est que tu n'as que deux choix (un nombre constant) à chaque fois. Ce n'est pas toujours le cas. J'espère que ça t'aide. J'ai repris ma première réponse pour ne pas créer de confusion sur ta proposition !
@@rechercheoperationnelle8907 Ah oui je vois tout à fait ! C'est le cas particulier qui permet cette petite stratégie. Tandis que la matrice de prédécesseurs marche avec n'importe quel dimension. :)
@@bertrandbaudeur5536 :) Oui, ce n'est pas facile d'expliquer ça en commentaires :). Ici on est d'accord que cela reste en O(nW) en théorie. Mais en pratique, c'est parfois le temps qui est limitant ou c'est la mémoire. Tout dépend de l'application donc il y a pas mal de stratégies possibles. Ta proposition me semble tout à fait correcte et intéressante. Son utilité va dépendre du contexte.
bonjour, j'ai une petite confusion dans le raisonnement, comment peut-on mettre un object de poids 2 dans un sac de capacité 0 ? ça me parait un peu contradictoire (8:25)
Bonjour Mehdi, Oui Merci je comprends que la phrase prête à confusion ! Pour reformuler: Le sous-problème courant a une capacité de 2 (celui qu'on traite) et on le résout en utilisant la valeur optimale du sous-problème de capacité 0 auquel on ajoute bien l'objet 1. Est plus clair ? J'espère qu'en regardant la suite, cela se clarifie pour toi.
Monsieur, pouvez-vous m'aider à résoudre deux exercices liés à la programmation dynamique? Je n'ai pas compris comment implémenter l'algorithme pour trouver les solutions.
Bonjour Achraf, Je ne sais pas bien comment t'aider mais si tu te connectes sur la plateforme, tu trouveras une implémentation de l'algorithme (que tu peux éxecuter en ligne) en java ou en python: sac à dos (python): moodle.caseine.org/mod/vpl/view.php?id=37086 sac à dos (java): moodle.caseine.org/mod/vpl/view.php?id=7415 Tu dois pouvoir te connecter en cliquant sur "connexion" puis "autres comptes universitaires". Si ça ne marche pas, tu m'envoies un mail hadrien.cambazard "at" grenoble-inp.fr et je te ferai un compte à la main. Le cours est ici: moodle.caseine.org/course/view.php?id=143 et les deux implémentations sont en haut de la section exercices (Knapsack). Tu peux accéder à la solution (le code) pour la manipuler, modifier, tester ce que tu veux.
merci pour la video mais, le faite de connaitre le chemin de la matrice p est ambigue le processus de connaitre le chemin vous faites a partir de matrice f plus tous que p
Une vidéo qui m'a bien rendu service !
En codant l'algorithme en Kotlin je n'obtenais pas le résultat attendu dans la matrice P car le premier encadré dans l'algorithme complet sur la vidéo (vers 12:12) est mal positionné.
La ligne qui le suit (renseigner f[C,i]) doit précéder les opérations réalisées dans l'encadré. Et ainsi ça fonctionne impeccablement. Merci !
Bonjour Win Ecran
Oui je crois que tu as raison. Une erreur d'indice s'est glissée dedans car j'ai du remettre en page l'algorithme pour gagner de la place et pour clarifier.
J'ai mis une petite correction en fin de description.
Il me semble que tu dois régler le problème (sans inverser les lignes) en remplaçant f[C,i] par f[C,i-1] dans le deuxième SI. Dis moi si ça marche ! Merci encore !
@@rechercheoperationnelle8907 Oui, comme ça c'est bon. Merci encore.
@@winecran215 Merci à toi :) !
Merci pour les vidéo, c'est très clair pour moi.
Super vidéo ! Les schémas rendent toutes les explications ludiques et claires.
Cependant j'aimerai ajouter quelque chose. Il me semble que pour trouver la solution à partir de la matrice des valeurs max de sac, il n'est pas nécessaire d'avoir une seconde matrice de prédécésseurs (qui double l'espace nécessaire au calcul).
Une autre méthode permet de trouver une solution optimale. La voici :
-On part de la dernière case notons la i,j, qui est de valeur optimale.
Pour chaque colonne.
-Si la case i,j-1 a la même valeur que la case actuelle. Alors on a pas pris l'objet j et on passe sur la case i,j-1.
Cela se conçoit par le fait que, rajouter le dernier objet dans l'équation n'a pas changé la valeur maximale du sac, donc ne pas le prendre revient au même.
Même si il est possible que l'arrivée du dernier objet ait changé l'organisation du sac (remplacements d'un ou plusieurs objet par le dernier). On a tout de même une solution optimale en ne le prenant pas.
-Sinon, on a pris l'objet j, donc on va à la case i-wj,j-1.
Cela se conçoit une fois de plus par le fait que prendre l'objet j dans l'équation a changé la valeur du sac, donc on l'a forcément mis dans le sac. Si ce n'est pas le cas c'est que la solution précédente aurait pu être meilleure, ce qui contredit hypothèse d'optimalité des cases de la matrice.
Un object de poids 0 ne change rien à cela puisqu'on irait alors sur la case i-0,j-1 en ayant bel et bien pris cet objet.
On repète cette opération jusqu'à arriver en 0,0
On pourrait argumenter sur le fait que cet algorithme ne suit pas forcément les choix fait durant le remplissage du tableau, ce qui est vrai. Mais :
-La solution est optimale donc on a ce qu'on cherche.
-L'algorithme de remplissage fait déjà des choix arbitraires en cas d'égalité des deux solutions. Seules cas ou la méthode de la seconde matrice et celle ci dessus peuvent diverger. Donc on a pas moins d'information dans un cas que dans l'autre.
Bonjour Stricorteur,
Merci de ton retour et de ta question, ça fait plaisir :)
Je suis tout à fait d’accord avec toi ! J’ajoute deux choses:
- Du point de vue de la complexité au pire cas, la consommation en espace (l’allocation mémoire pour la table) est en O(nW). Un x2 ("fois deux") ne change rien de ce point de vue. En pratique en revanche, tu as raison cela peut faire une grosse différence.
(je n'avais pas bien compris ce que tu disais, j'essaie donc de clarifier pour éviter la confusion :))
- En faisant ce que tu proposes, tu pars d'une case optimale finale et tu re-testes les deux choix à chaque fois en remontant de colonnes en colonnes (tu re-calcules le max n fois) mais cela reste bien en O(n). Cela ne coûte pas plus cher que de parcourir la table des prédécesseurs p à la fin pour sortir une solution optimale i.e O(n). En revanche plus l’algorithme va être couteux en temps (si au lieu de deux cases à évaluer à chaque fois, tu en as n par exemple un max à faire sur n case) alors cela va devenir un plus coûteux. Il peut du coup devenir intéressant (dans d'autres programmes dynamique) de stocker le résultat dans p pour éviter de refaire ces calculs « en arrière » à la fin.
Donc globalement cet algorithme (ou ta proposition) est en O(nW) en espace et aussi en temps. Et dans le cas précis du sac à dos, ta proposition pourrait bien être plus rapide en pratique car allouer de la mémoire prends aussi du temps :)
Par contre, il y a des cas ou on peut réduire la complexité spatiale au prix d'une petite augmentation de la complexité temporelle. Si cela t'intéresse (va d'abord au bout de ton cours de prog. dyn), tu peux aller regarder l'exercice 6.24 (Time and space complexity of dynamic programming) de ce livre: people.eecs.berkeley.edu/~vazirani/algorithms/chap6.pdf
Enfin Il aussi existe d'autre façon d'implémenter la table pour éviter d'allouer toute cette mémoire et améliorer en pratique. Cette grosse matrice est souvent très creuse en réalité. Nous avons fait ici vraiment la base. J'espère faire quelques vidéos pour aller plus loin et détailler tout ça.
J'espère que j'ai bien compris ce que tu disais !
Bonne journée
Hadrien
@@rechercheoperationnelle8907 Merci pour ces explications, cependant il me semble que dans ma stratégie, remonter la table se passe également en O(n).
La colonne sur laquelle on travail décroit strictement à chaque itération. On a donc au plus n vérification et affectations. Voici un exemple d'exécution sur l'exemple de la vidéo à 10:07 :
On commence à la case (10,5).
case(10,5) = case(10,4) ? OUI -> on part sur la case (10,4) et l'objet 5 n'est pas pris.
On est sur (10,4).
case(10,4) = case(10,3) ? NON -> on passe sur la case(10-w4,3) soit case(6,3) et l'objet 4 est pris.
On est sur (6,3).
case(6,3) = case(6,2) ? NON -> on passe sur la case(6-w3,2) soit case(2,2) et l'objet 3 est pris.
On est sur (2,2).
case(2,2) = case(2,1) ? OUI -> on passe sur la case(2,1) et 2 n'est pas pris.
On est sur la case(2,1).
case(2,1) = case(2,0) ? NON -> on passe sur la case(2-w1,0) soit case(0,0) et l'objet 1 est pris.
L'algorithme est terminé.
On a donc pris les objets 1,3,4. Ce qui est bien notre solution optimale. Le parcours s'est fait en 5 étape.
On aurait donc O(nW + n) = O(nW) en temps.
N'hésitez pas à me reprendre si une faille se trouve dans mon raisonnement.
J'essaierai d'aller voir l'exercice du livre si je trouve le temps.
@@bertrandbaudeur5536 Ah ok je vois mieux, tout à fait ! Effectivement si tu fais ça c'est en O(n), pas de soucis !
Donc pour faire la différence, imagine que tu as n cases à vérifier avant et pas juste 2, ta stratégie pour "détricoter" est dans ce cas en O(n^2) et va dans ce cas couter un peu plus cher. Je voulais juste faire cette différence pour dire que si tu n'a pas de problème de mémoire, stocker le meilleur choix peut t'éviter ce recalcul.
Ce qui est "particulier" ici c'est que tu n'as que deux choix (un nombre constant) à chaque fois. Ce n'est pas toujours le cas.
J'espère que ça t'aide.
J'ai repris ma première réponse pour ne pas créer de confusion sur ta proposition !
@@rechercheoperationnelle8907 Ah oui je vois tout à fait ! C'est le cas particulier qui permet cette petite stratégie. Tandis que la matrice de prédécesseurs marche avec n'importe quel dimension. :)
@@bertrandbaudeur5536 :) Oui, ce n'est pas facile d'expliquer ça en commentaires :).
Ici on est d'accord que cela reste en O(nW) en théorie. Mais en pratique, c'est parfois le temps qui est limitant ou c'est la mémoire. Tout dépend de l'application donc il y a pas mal de stratégies possibles.
Ta proposition me semble tout à fait correcte et intéressante. Son utilité va dépendre du contexte.
bonjour, j'ai une petite confusion dans le raisonnement, comment peut-on mettre un object de poids 2 dans un sac de capacité 0 ? ça me parait un peu contradictoire (8:25)
Bonjour Mehdi,
Oui Merci je comprends que la phrase prête à confusion !
Pour reformuler: Le sous-problème courant a une capacité de 2 (celui qu'on traite) et on le résout en utilisant la valeur optimale du sous-problème de capacité 0 auquel on ajoute bien l'objet 1. Est plus clair ?
J'espère qu'en regardant la suite, cela se clarifie pour toi.
@@rechercheoperationnelle8907 c'est très clair maintenant. merci !
Monsieur, pouvez-vous m'aider à résoudre deux exercices liés à la programmation dynamique? Je n'ai pas compris comment implémenter l'algorithme pour trouver les solutions.
Bonjour Achraf,
Je ne sais pas bien comment t'aider mais si tu te connectes sur la plateforme, tu trouveras une implémentation de l'algorithme (que tu peux éxecuter en ligne) en java ou en python:
sac à dos (python): moodle.caseine.org/mod/vpl/view.php?id=37086
sac à dos (java): moodle.caseine.org/mod/vpl/view.php?id=7415
Tu dois pouvoir te connecter en cliquant sur "connexion" puis "autres comptes universitaires". Si ça ne marche pas, tu m'envoies un mail hadrien.cambazard "at" grenoble-inp.fr et je te ferai un compte à la main.
Le cours est ici: moodle.caseine.org/course/view.php?id=143 et les deux implémentations sont en haut de la section exercices (Knapsack). Tu peux accéder à la solution (le code) pour la manipuler, modifier, tester ce que tu veux.
@@rechercheoperationnelle8907 ok, mérci beaucoup
merci pour la video mais, le faite de connaitre le chemin de la matrice p est ambigue le processus de connaitre le chemin vous faites a partir de matrice f plus tous que p
Oui je suis d accord qu il faudrait clarifier davantage l obtention de la solution elle même.