Dans une conférence précédente, on nous a dit que l'utilisation d'une approche gourmande pour résoudre un problème de changement ne fonctionnerait pas toujours.Changement: Programmation dynamique
Un exemple a été donné comme suit:
Nous voulons atteindre n = 14, et nous avons trois pièces de différentes valeurs: d1 = 1, d2 = 7, d3 = 10. En utilisant l'approche gloutonne cela nous conduirait à 10 + 1 + 1 + 1 + 1 (5 pièces).
On a dit que l'approche d'un problème dynamique permettrait de résoudre ce problème avec précision. J'ai essayé de travailler dehors, mais il est revenu à 5.
On suppose F détient le nombre de pièces nécessaires pour faire un montant
F[14] = min {F[14 – 1] , F[14 – 7], F[14 – 10]} + 1
= F[14 – 10] + 1 = 4 + 1 = 5
Cela montre encore une fois que nous avons besoin de 5 pièces, lorsque cela peut être clairement fait en utilisant 2 pièces (7 + 7).
Ce qui donne? Merci.
F [14] = min {F [14 - 1], F [14-7], F [14-10]} + 1 = F [14 - 10] + 1 = 4 + 1 = 5 cela ne devrait-il pas être F [14] = min {F [14 - 1], F [14 - 7], F [14 - 10]} + 1 = F [14 - 7] + 1 = 1 + 1 = 2 –