4.1. Método general.

Devolver-cambio (P: integer; C: array [1..N] of integer; var X: array [1..N] of integer);

act:= 0;

for i:= 1 to N do

X[i]:= 0;

while act ? P do begin

j:= el mayor elemento de C tal que C[j] ? (P - act);

if j=0 then { Si no existe ese elemento }

return “No existe solución”;

X[j]:= (P - act) div C[j];

act:= act + C[j]*X[j];

end;

• ¿Cuál será el orden de complejidad del algoritmo?

• Para este sistema monetario encuentra siempre la solución óptima. Sin embargo, ¿encuentra siempre la solución óptima?

• Ejemplo, supongamos que tenemos monedas de 100, 90 y 1. Queremos devolver 180.

  • Algoritmo voraz: 1 moneda de 100 y 80 monedas de 1: total 81 monedas.
  • Solución óptima: 2 monedas de 90: total 2 monedas.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica