Article View: es.comp.os.linux.programacion
Article #9580Re: Algoritmo de cambio de monedas [largo y un poco offtopic, lo tiene todo]
From: David Hernandez
Date: Thu, 13 Jun 2002 13:47
Date: Thu, 13 Jun 2002 13:47
41 lines
2198 bytes
2198 bytes
En el art�culo <20020613.145806.146670071.1287@verde.es>, Mario Galan escribi�: > > Pero no funcionar�a con: > > 1,4,5,8,... porque la moneda de valor 4 es mayor a la mitad de la > moneda de valor superior 5. El �nico requisito de ese algoritmo(echo por voraces) es que haya monedas de valor 1. > Por otra parte existe un algoritmo mediante programaci�n din�mica para el > cambio de monedas que siempre funciona pero no es aplicable a casos > reales por el costo espacial y temporal que implica. > Con monedas de valor 1 ese algoritmo proporciona el �ptimo con lo cual no hace falta aplicar din�mica. El psuedocodigo del algortimo se adapta al esquema de voraces es muy sencillo. mientras cambio no exacto hacer si (cambio- moneda mayor valor)>=0 a�adir moneda a solucion; cambio=cambio-moneda mayor valor; sino actualiza moneda mayor valor; fmientras Hace tiempo que no miro lo de voraces (desde que aprov� :-) Pero m�s o menos es eso. Saludos
Technical Details
Message-ID:
<slrnagh8qk.mn.xsidius@dhp.net.dhis.org>Path:
arc1-ca.pugleaf.net!archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!colt.net!newsfeed.icl.net!mango.news.easynet.net!easynet-melon!easynet.net!news.rediris.es!newsfeed.bt.es!newsfeed.telecable.es!not-for-mailReferences:
<20020613.145806.146670071.1287@verde.es>Show Full Headers
Complete Article Headers
X-Google-Language: SPANISH,ASCII X-Google-Thread: f86c8,4ab1a3edb56d2d07 X-Google-Attributes: gidf86c8,public X-Google-ArrivalTime: 2002-06-13 06:51:34 PST Path: arc1-ca.pugleaf.net!archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!colt.net!newsfeed.icl.net!mango.news.easynet.net!easynet-melon!easynet.net!news.rediris.es!newsfeed.bt.es!newsfeed.telecable.es!not-for-mail From: David Hernandez <xsidius@escomposlinux.org> Newsgroups: es.comp.os.linux.programacion Subject: Re: Algoritmo de cambio de monedas [largo y un poco offtopic, lo tiene todo] Date: Thu, 13 Jun 2002 13:47:24 +0000 (UTC) Organization: Telecable S.A. Lines: 42 Message-ID: <slrnagh8qk.mn.xsidius@dhp.net.dhis.org> References: <20020613.145806.146670071.1287@verde.es> NNTP-Posting-Host: cm17281.telecable.es Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: filemon2.isp.telecable.es 1023976044 17017 81.9.140.15 (13 Jun 2002 13:47:24 GMT) X-Complaints-To: abuse@telecable.es NNTP-Posting-Date: Thu, 13 Jun 2002 13:47:24 +0000 (UTC) User-Agent: slrn/0.9.7.4 (Linux)