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 A461AD176 for ; Sun, 31 Jul 2005 19:29:04 +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 j6VHT4Wl028081 for ; Sun, 31 Jul 2005 19:29:04 +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 TAA21788 for ; Sun, 31 Jul 2005 19:29:03 +0200 (MET DST) Received: from smtp8.wanadoo.fr (smtp8.wanadoo.fr [193.252.22.23]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6VHT3E0028077 for ; Sun, 31 Jul 2005 19:29:03 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf0802.wanadoo.fr (SMTP Server) with ESMTP id 35A921C00274 for ; Sun, 31 Jul 2005 19:29:03 +0200 (CEST) Received: from oemcomputer (Mix-Lyon-302-4-146.w193-248.abo.wanadoo.fr [193.248.231.146]) by mwinf0802.wanadoo.fr (SMTP Server) with SMTP id C73161C00262; Sun, 31 Jul 2005 19:29:01 +0200 (CEST) X-ME-UUID: 20050731172901816.C73161C00262@mwinf0802.wanadoo.fr Message-ID: <004401c595f5$1f131e80$92e7f8c1@oemcomputer> From: "alphablock" To: "Diego Olivier Fernandez Pons" , References: Subject: =?iso-8859-1?Q?Re:_=5BCaml-list=5D_Probl=E8me=5Fde=5Fl'achat=5Fpar=5Flots?= Date: Sun, 31 Jul 2005 19:26:00 +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 42ED0A60.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42ED0A5F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 l'intuition:01 m'interesse:01 damien:01 pons:01 pons:01 caml-list:01 damien:01 implementer:01 depasser:01 minimise:01 resoudre:01 lineaire:01 entiers:01 enumeration: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 Bonsoir, Vous n'avez pas trouvé le code Caml ? C'est la fonction "place_order", en bas de page, sur un fond-cadre légèrement grisé. En fait j'ai programmé cette fonction "à l'intuition" et je suis bien incapable de dire à quelle catégorie de solution elle appartient (l'autodidacte a toujours ses lacunes). Ce que je peux affirmer c'est que je l'ai testée sur des exemples non triviaux dans le domaine qui m'intéresse (décomposition d'une maquette lego en un inventaire de boîtes de legos à acheter) et qu'elle fonctionne à merveille. Reste à savoir comment elle va se comporter en performance quand le catalogue va grossir jusqu'à plus de 6500 boîtes legos connues. Si vous en avez une idée, ne vous privez pas de la partager. Ma page d'exercice http://www.ocaml-tutorial.org/implement_an_inventory_facility est sur un Wiki, donc éditable, si vous trouvez un meilleur lien pour le problème du sac à dos, vous pouvez cliquer sur [edit]. Considérations, - damien ----- Original Message ----- From: "Diego Olivier Fernandez Pons" To: Cc: Sent: Sunday, July 31, 2005 5:21 PM Subject: Re: [Caml-list] Problème_de_l'achat_par_lots 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 _______________________________________________ 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