From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 347B2D176 for ; Sun, 31 Jul 2005 15:50:22 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6VDoLdM012869 for ; Sun, 31 Jul 2005 15:50:21 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA19408 for ; Sun, 31 Jul 2005 15:50:21 +0200 (MET DST) 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 j6VDoK58012866 for ; Sun, 31 Jul 2005 15:50:21 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf1207.wanadoo.fr (SMTP Server) with ESMTP id D284B1C000AD for ; Sun, 31 Jul 2005 15:50:20 +0200 (CEST) Received: from compaqm700 (Mix-Lyon-303-4-188.w193-248.abo.wanadoo.fr [193.248.106.188]) by mwinf1207.wanadoo.fr (SMTP Server) with SMTP id 656C81C000AB; Sun, 31 Jul 2005 15:50:19 +0200 (CEST) X-ME-UUID: 20050731135019415.656C81C000AB@mwinf1207.wanadoo.fr Message-ID: <004101c595d6$1b49f9a0$d45efea9@compaqm700> From: "Damien Guichard" To: Cc: References: Subject: =?iso-8859-1?Q?Re:_=5BCaml-list=5D_Probl=E8me=5Fde=5Fl'achat=5Fpar=5Flots?= Date: Sun, 31 Jul 2005 15:45:25 +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 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 X-Miltered: at nez-perce with ID 42ECD71D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42ECD71C.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; damien:01 caml-list:01 implementer:01 l'exercice:01 damien:01 pons:01 pons:01 caml-list:01 manquantes:01 tombe:01 vois:01 resoudre:01 implementer:01 minimiser:01 lineaire:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 merci pour votre assistance. 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. 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 considérations, - damien ----- Original Message ----- From: "Diego Olivier Fernandez Pons" To: Cc: Sent: Sunday, July 31, 2005 1:46 PM Subject: [Caml-list] Re: Problème_de_l'achat_par_lots Bonjour, Damien a écrit : > 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) ? Désolé de ne répondre que maintenant, j'ai n'ai pas vu le message initial passer, ce n'est qu'en fouillant dans les archives que je suis tombé dessus. > 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 ? Il y a deux problèmes dans votre question : i) le permier est un problème d'optimisation (quel est le problème a résoudre ? avec quel type de méthode ?) ii) le second est un problème d'implantation (comment implémenter en Caml la méthode choisie en i) i. Le problème d'optimisation Votre problème est en gros un problème de "covering". Dans un problème de covering on cherche à minimiser le coût total d'achat sachant qu'on veut satisfaire (couvrir) la demande. Dans votre problème on ne cherche pas à satisfaire toute la demande, mais une sorte de distance (somme de excédents et des déficits) et on divise par le coût. plusieurs méthodes : - programmation linéaire en nombres entiers (PLNE) - énumération implicite, programmation par contraintes (PPC) Si vous n'êtes pas familier avec la PLNE, il vaut mieux ne pas choisir cette méthode, surtout si vous voulez implémenter ensuite en Caml (c'est compliqué et ça utilise plein de flottants). ii. Implémentation en Caml d'une méthode d'énumération implicite Il énumérer intelligement toutes les combinaisons possibles. Pour cela, il faut un mécanisme de réversibilité qui s'obtient facilement en Caml par - des appels de fonctions récursives - des structures de données persistantes (librairie standard) - des exceptions J'avais donné un exemple pour le subset sum (trouver un sous-ensemble d'éléments ayant une somme fixe S) dans comp.lang.functional (Backtracking in Haskell), code à la fin du message. la procédure de base est simple : - on prend le premier lot - on essaye en l'ajoutant au panier (appel récursif fonction) - on essaye en l'interdisant dans le panier (appel récursif fonction) Dans chaque sous-cas on fait des calculs pour éliminer le plus de lots dont l'ajout au panier ne sert à rien (par exemple touts les demandes ont été satifaites) ou ajouter ceux qui sont nécessaires. Quand on aboutit à une impasse, on lève une exception. Le code risque d'être un peu plus complexe que pour le subset-sum mais les principes sont les mêmes. (* Code pour le subsetsum problem *) exception Fail let rec subsetsum = fun remaining candidates -> match remaining with | 0 -> [] | _ -> match candidates with | v :: tail when v <= remaining -> (try v :: subsetsum (remaining - v) tail with Fail -> subsetsum remaining tail ) | _ -> raise Fail # subsetsum 40 [3;8;9;13;12;15;17;19];; - : int list = [3; 8; 14; 15] Diego Olivier _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs