Le sac à dos indivisible, ou la chute du glouton

Sur les données de l'énoncé, seul le critère « poids croissant » échoue ($4+5$ kg, valeur $44$, contre $54$ pour les objets de $6$ et $4$ kg) ; valeur et densité décroissantes y trouvent l'optimum, d'où les autres instances. Considérons les trois critères gloutons classiques :

1. Valeur décroissante : Sur l'instance de capacité $10$ avec objets $(7\text{ kg},42)$, $(5\text{ kg},25)$, $(5\text{ kg},25)$ : le glouton choisit l'objet de valeur $42$ et ne peut plus rien ajouter (valeur $42$). L'optimalité est de prendre les deux objets de poids $5$ pour une valeur cumulée de $50$.
2. Densité de valeur décroissante : Sur la même instance, les densités sont de $42/7=6$ et $25/5=5$. Le glouton choisit en priorité l'objet de densité $6$, ce qui mène au même échec (valeur $42$ vs $50$).
3. Poids croissant : Sur l'instance de capacité $10$ avec objets $(4\text{ kg},8)$, $(5\text{ kg},9)$, $(10\text{ kg},30)$ : le glouton par poids croissant sélectionne l'objet de poids $4$ puis celui de poids $5$, soit une valeur de $17$. L'optimum est de choisir uniquement l'objet de poids $10$ pour une valeur de $30$. En conclusion, le problème du sac à dos indivisible ne peut pas être résolu de manière optimale par une stratégie gloutonne générale.