Enigme chameau bananes

Salut, je pense que tout le monde connaît l'énigme suivante :

"Un marchand possède 3000 bananes, il souhaite les vendre au marché qui se trouve à 1000 km de là. Pour les transporter, il dispose d'un chameau assez particulier puisque cet animal n'est pas capable de transporter plus de 1000 bananes à la fois et qu'en plus, le chameau mange une banane par kilomètre !

Combien de bananes le marchand est-il en mesure d'amener au marché ?

(Il a la possibilité de faire autant de trajets qu'il souhaite et peut déposer des bananes en chemin et les reprendre ensuite.)"


Bon la solution est 533, j'ai trouvé un moyen d'amener 533 bananes et l'algo utilisé me paraît assez naturellement optimal. Sauf que je sais pas du tout quelle est la théorie derrière, comment justifier rigoureusement que c'est le meilleur algorithme, et je n'ai aucune idée de comment faire un traitement systématique du problème (si on a N bananes, qu'on peut en porter P et qu'il y a X kilomètres à faire). Quelqu'un a des références sur ce genre de problèmes ?

Réponses

Connectez-vous ou Inscrivez-vous pour répondre.