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 DA4AED176 for ; Sun, 31 Jul 2005 17:21:54 +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 j6VFLsbG019478 for ; Sun, 31 Jul 2005 17:21:54 +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 RAA20431 for ; Sun, 31 Jul 2005 17:21:53 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6VFLrMe019470 for ; Sun, 31 Jul 2005 17:21:53 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id j6VFLrP5079170 ; Sun, 31 Jul 2005 17:21:53 +0200 (CEST) X-Ids: 166 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id RAA50194 ; Sun, 31 Jul 2005 17:18:04 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id RAA2261216 ; Sun, 31 Jul 2005 17:21:23 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Sun, 31 Jul 2005 17:21:22 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: caml-list@inria.fr Cc: damien.guichard@wanadoo.fr Subject: =?iso-8859-1?Q?Re:_=5BCaml-list=5D_Probl=E8me=5Fde=5Fl'achat=5Fpar=5Flots?= In-Reply-To: <004101c595d6$1b49f9a0$d45efea9@compaqm700> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.166]); Sun, 31 Jul 2005 17:21:53 +0200 (CEST) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at nez-perce with ID 42ECEC92.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42ECEC91.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 42ECEC91.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 caml-list:01 implementer:01 depasser:01 minimise:01 resoudre:01 lineaire:01 entiers:01 enumeration:01 implicite:01 l'exercice:01 l'exercice:01 interessante:01 implicite: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 Bonjour, > Cepandant j'ai choisi la m=E9thode du "backpack problem" (probl=E8me du > sac-=E0-dos), bien plus facile =E0 impl=E9menter, et j'en ai fait un > exercice visible sur http://www.ocaml-tutorial.org. Traditionnellement, on dit plut=F4t knapsack (probl=E8me du sac =E0 dos), c'est la terminologie adopt=E9e par les ouvrages de r=E9f=E9rence : - Knapsack problems. Martello et Toth 1990 - Knapsack problems. Kellerer, Pferschy et Pisinger 2003 Les probl=E8mes de packing et de covering sont sym=E9triques : dans le premier cas on maximise le co=FBt sans d=E9passer la borne (sac =E0 dos), dans l'autre on minimise le co=FBt sans passer en dessous de la borne (set-cover). Votre probl=E8me est proche des deux classes sans s'y mouler vraiment. Cela dit, pour r=E9soudre le probl=E8me de sac =E0 dos il y a (encore et toujours) 3 m=E9thodes : - programmation lin=E9aire en nombres entiers - =E9num=E9ration implicite - programmation dynamique Je n'avais pas cit=E9 la derni=E8re dans mon courrier pr=E9c=E8dent car je = ne sais pas si elle est appliquable =E0 votre probl=E8me sp=E9cifique. Notez =E9galement que subset-sum problem pour lequel j'ai fourni du code Caml est un cas particulier de knapsack. > voir ici l'=E9nonc=E9 de l'exercice et la solution =E0 l'aide de la > m=E9thode du sac-=E0-dos: > > http://www.ocaml-tutorial.org/implement_an_inventory_facility > Je n'ai pas trouv=E9 de code Caml. La page que vous pointez dans l'exercice est tr=E8s int=E9ressante : l'auteur dit qu'utiliser une m=E9thode d'=E9num=E9ration implicite est trop lourd pour le probl=E8me de sac =E0 dos, il propose donc une m=E9thode ... d'=E9num=E9ration implicite. Diego Olivier