5.3.1. Problema del cambio de monedas.

• Algoritmo.

Devolver-cambio (P: int; C: array [1..n] of int; var D: array [1..n, 0..P] of int);

for i:= 1 to n do

D[i, 0]:= 0;

for i:= 1 to n do

for j:= 1 to P do { Tener en cuenta si el valor }

D[i, j]:= min ( D[i-1, j] , D[i, j - C[i]] + 1 ); { cae fuera de la tabla. }

• Ejemplo. n= 3, P= 8, c= (1, 4, 6)

• ¿Cuál es el tiempo de ejecución del algoritmo?

• ¿Cómo es en comparación con el algoritmo voraz?

• D[n, P]: número mínimo de monedas que hay que usar para devolver la cantidad P.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica