Re: [Caml-list] Problème_de_l'achat_par_lots

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> Cepandant j'ai choisi la méthode du "backpack problem" (problème du
> sac-à-dos), bien plus facile à implémenter, et j'en ai fait un
> exercice visible sur http://www.ocaml-tutorial.org.

Traditionnellement, on dit plutôt knapsack (problème du sac à dos),
c'est la terminologie adoptée par les ouvrages de référence :
- Knapsack problems. Martello et Toth 1990
- Knapsack problems. Kellerer, Pferschy et Pisinger 2003

Les problèmes de packing et de covering sont symétriques : dans le
premier cas on maximise le coût sans dépasser la borne (sac à dos),
dans l'autre on minimise le coût sans passer en dessous de la borne
(set-cover).

Votre problème est proche des deux classes sans s'y mouler vraiment.

Cela dit, pour résoudre le problème de sac à dos il y a (encore et
toujours) 3 méthodes :
- programmation linéaire en nombres entiers
- énumération implicite
- programmation dynamique

Je n'avais pas cité la dernière dans mon courrier précèdent car je ne
sais pas si elle est appliquable à votre problème spécifique.

Notez également que subset-sum problem pour lequel j'ai fourni du code
Caml est un cas particulier de knapsack.

> voir ici l'énoncé de l'exercice et la solution à l'aide de la
> méthode du sac-à-dos:
>
> http://www.ocaml-tutorial.org/implement_an_inventory_facility
>

Je n'ai pas trouvé de code Caml.

La page que vous pointez dans l'exercice est très intéressante :
l'auteur dit qu'utiliser une méthode d'énumération implicite est trop
lourd pour le problème de sac à dos, il propose donc une méthode ...
d'énumération implicite.


        Diego Olivier