From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id B3E5BBCAF for ; Sun, 3 Jul 2005 22:43:31 +0200 (CEST) Received: from smtp12.wanadoo.fr (smtp12.wanadoo.fr [193.252.22.20]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j63KhVAQ019131 for ; Sun, 3 Jul 2005 22:43:31 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf1207.wanadoo.fr (SMTP Server) with ESMTP id 5197D1C00058 for ; Sun, 3 Jul 2005 22:43:31 +0200 (CEST) Received: from oemcomputer (Mix-Lyon-302-4-123.w193-248.abo.wanadoo.fr [193.248.231.123]) by mwinf1207.wanadoo.fr (SMTP Server) with SMTP id 6CC8F1C00056 for ; Sun, 3 Jul 2005 22:43:30 +0200 (CEST) X-ME-UUID: 20050703204330445.6CC8F1C00056@mwinf1207.wanadoo.fr Message-ID: <002801c5800f$ab1d0e00$a22cf8c1@oemcomputer> From: "alphablock" To: "caml-list" Subject: =?iso-8859-1?Q?Probl=E8me_de_l'achat_par_lots?= Date: Sun, 3 Jul 2005 22:41:23 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 X-Miltered: at nez-perce with ID 42C84DF3.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; defini:01 paires:01 renvoit:01 manquantes:01 rec:01 rec:01 implementer:01 manquantes:01 vois:01 damien:01 est-ce:01 est-ce:01 int:01 match:02 match:02 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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/