Le glouton fractionnaire qui a raison

Puisque les denrées sont fractionnables, le critère optimal est le tri par densité de valeur (valeur/poids) :

• Denrée 1 : $30/6=5$ /kg
• Denrée 2 : $20/5=4$ /kg
• Denrée 3 : $24/4=6$ /kg. L'algorithme trie les denrées par densité décroissante : Denrée 3, puis Denrée 1, puis Denrée 2.
• Prendre la totalité de la Denrée 3 ($4$ kg, valeur $=24$). Reste $6$ kg.
• Prendre la totalité de la Denrée 1 ($6$ kg, valeur $=30$). Reste $0$ kg. Le sac est rempli avec une valeur totale maximale de $24+30=54$. Un critère "plus lourd d'abord" conduirait à choisir l'objet 1 ($6$ kg, valeur $30$) puis $4$ kg de l'objet 2 ($4\times 4=16$), soit $46$, ce qui est sous-optimal.