Ce qui casse quand les activités sont pondérées

Non, et il s'effondre. Le plus petit contre-exemple tient en deux activités :

Sur la première, le glouton prend $[0,5[$ parce qu'elle finit plus tôt, et perd un facteur $100$. Sur $20000$ instances de quatre activités tirées au hasard, il s'est trompé $10127$ fois, soit $50,6\%$.

Pourquoi la preuve du cours ne survit pas. L'argument d'échange remplaçait $o_1$ par $g_1$ « sans diminuer le cardinal ». Avec des poids, l'échange remplace $w_{o_1}$ par $w_{g_1}$, et rien ne dit que $w_{g_1}\ge w_{o_1}$ : l'activité qui finit le plus tôt peut être la moins rémunératrice. L'étape 2 du patron — « substituer sans perdre en qualité » — est fausse, et le patron tombe avec elle.

Aucun glouton ne marche. On pourrait essayer « le poids le plus fort d'abord » : il échoue sur $[0,10[$ de poids $11$ contre $[0,4[$ de poids $6$ et $[5,9[$ de poids $6$, qui totalisent $12$. Ou « le meilleur rapport poids/durée » : il échoue aussi. C'est structurel, et non un manque d'imagination.

La méthode qui résout ce problème est la programmation dynamique du chapitre chap:dynamique — le programme cite d'ailleurs l'« ordonnancement de tâches pondérées » précisément dans cette rubrique. On trie par fin croissante, on note $q(i)$ le plus grand indice $j<i$ compatible avec $i$, et

$$M(i)=\max (M(i-1),w_i+M(q(i))),$$

en $\Theta (n\log n)$ — le tri, plus une recherche dichotomique par activité pour $q(i)$.

La leçon. Le cas non pondéré est le cas pondéré avec tous les poids égaux à $1$. Un glouton exact peut donc être exactement le cas particulier d'un problème que la méthode gloutonne ne sait pas résoudre. Devant un problème d'optimisation, avant d'écrire un glouton, il faut donc chercher si une généralisation naturelle le casse : si oui, l'optimalité tenait à une coïncidence, et il faut la démontrer avec soin — ou bien changer de méthode.