Problème de l'achat par lots

["alphablock" <alphablock@wanadoo.fr>]

Bonsoir à tous les chameliers,


J'ai défini un type "inventaire" qui est une liste de paires
(quantité,pièce) ainsi que 2 opérations de base. Les listes sont triées
selon le nom des pièces. La 1ère opération réalise l'union de deux
inventaires, la 2nd opération réalise la différence de deux inventaires et
renvoit une paire de listes (pièces restantes,pièces manquantes) :


type inventory = (int * string) list;;

let rec union_inventory (a:inventory) (b:inventory) =
  match a,b with
  | [],_ -> b
  | _,[] -> a
  | (qa,pa as ha)::ta,(qb,pb as hb)::tb ->
      if pa < pb then ha::(union_inventory ta b)
      else if pa > pb then hb::(union_inventory a tb)
      else (qa+qb,pa)::(union_inventory ta tb);;

let rec difference_inventory (a:inventory) (b:inventory) =
  match a,b with
  | [],_ -> [],b
  | _,[] -> a,[]
  | (qa,pa as ha)::ta,(qb,pb as hb)::tb ->
      if pa < pb then
        let r,m = difference_inventory ta b
        in  ha::r,m
      else if pa > pb then
        let r,m = difference_inventory a tb
        in  r,hb::m
      else
        let r,m = difference_inventory ta tb in
        if qa < qb then r,(qb-qa,pa)::m
        else if qa > qb then (qa-qb,pa)::r,m
        else r,m;;


Maintenant je voudrais implémenter une opération plus complexe. Soit un
inventaire recherché par un achateur, et soit une liste de lots-inventaires
en vente. L'acheteur veut maximiser son investissement, c'est-à-dire avoir
le moins de pièces manquantes possible et le moins de pièces supperflues
possible. Comment trouver la(les) combinaison(s) de lots la(les) plus
avantageuse(s) ?

Je ne vois pas bien comment il faut aborder le problème:
* est-ce un "backpack problem" ?
* est-ce un "union-find problem" ?
* est-ce un "genetic-oriented problem" ?
* sinon qu'est-ce que c'est ?

merci de votre aide,

- damien

web page: http://perso.wanadoo.fr/alphablock/