Monedas algoritmos ávidos

EL PROBLEMA DEL CAMBIO
Suponiendo que el sistema monetario de un país está formado por monedas de
valores v1,v2,...,vn, el problema del cambio de dinero consiste en descomponer
cualquier cantidaddada M en monedas de ese país utilizando el menor número
posible de monedas.
En primer lugar, es fácil implementar un algoritmo ávido para resolver este
problema, que es el que sigue el proceso queusualmente utilizamos en nuestra vida
diaria. Sin embargo, tal algoritmo va a depender del sistema monetario utilizado y
por ello vamos a plantearnos dos situaciones para las cuales deseamosconocer si el
algoritmo ávido encuentra siempre la solución óptima:
a) Suponiendo que cada moneda del sistema monetario del país vale al menos el
doble que la moneda de valor inferior, que existe unamoneda de valor unitario,
y que disponemos de un número ilimitado de monedas de cada valor.
b) Suponiendo que el sistema monetario está compuesto por monedas de valores 1,
p, p2, p3,..., pn, donde p >1 y n > 0, y que también disponemos de un número
ilimitado de monedas de cada valor.
Solución ()
Comenzaremos con la implementación de un algoritmo ávido que resuelve el
problema del cambio dedinero:
144 TÉCNICAS DE DISEÑO DE ALGORITMOS
TYPE MONEDAS =(M500,M200,M100,M50,M25,M5,M1);(*sistema monetario*)
VALORES = ARRAY MONEDAS OF CARDINAL; (* valores de monedas *)
SOLUCION = ARRAY MONEDASOF CARDINAL;
PROCEDURE Cambio(n:CARDINAL;VAR valor:VALORES;VAR cambio:SOLUCION);
(* n es la cantidad a descomponer, y el vector "valor" contiene los
valores de cada una de las monedas del sistemamonetario *)
VAR moneda:MONEDAS;
BEGIN
FOR moneda:=FIRST(MONEDAS) TO LAST(MONEDAS) DO
cambio[moneda]:=0
END;
FOR moneda:=FIRST(MONEDAS) TO LAST(MONEDAS) DO
WHILE valor[moneda] 0. Tal cantidadha de ser par pues
x – r0 lo es (por la expresión [4.2]). Y por ser par, siempre podremos “mejorar” la
segunda descomposición (s0,s1,...,sn) cambiando s0 – r0 monedas de 1 unidad por
(s0 – r0)/2...