sujet Test 6 : gloutons
Auteur :
- François Brucker
Un cambrioleur entre par effraction dans une boutique de poudres de perlimpinpin.
La boutique propose $n$ poudres différentes, chaque poudre $i$ étant décrite par :
- sa quantité sur l'étal (en kilo): $k_i$
- son prix au kilo : $p_i$
Le cambrioleur dispose d'un sac pouvant contenir K kilos de poudre et il veut repartir avec le plus de butin (en prix) possible.
- proposer un algorithme glouton pour résoudre le problème
- démontrez qu'en choisissant les poudres par prix au kilo décroissant, l'algorithme est optimal