Glouton ou table ? Le discernement final

(a) Glouton : Le système de l'Euro est canonique. On peut prouver par argument d'échange que le choix systématique de la plus grande pièce disponible mène à l'optimum. (b) Programmation dynamique : Le choix glouton peut s'enfermer dans des solutions sous-optimales ou échouer à trouver un rendu (ex : $\{10,7,1\}$ pour $14$). Il est nécessaire d'essayer tous les choix possibles via une table. (c) Glouton : Le choix systématique de la tâche compatible qui se termine le plus tôt laisse le maximum d'espace pour les tâches suivantes, ce qui est optimal pour maximiser le nombre total de tâches. (d) Programmation dynamique : L'introduction de gains arbitraires invalide l'argument d'échange glouton. Il faut utiliser la récurrence $G(i)=\max (G(i-1),gai{n}_i+G(p(i)))$. (e) Glouton : L'algorithme de Dijkstra est fondamentalement glouton. Il effectue un choix local sûr en figeant à chaque étape le sommet possédant la distance provisoire minimale. (f) Programmation dynamique : La présence de poids négatifs invalide le choix local de Dijkstra. L'algorithme de Floyd-Warshall (ou de Bellman-Ford) utilise une récurrence systématique sur les chemins pour garantir l'optimalité globale.