[ Foro de C++ ]
Se tiene un sistema de billetes de distintos valores y ordenados de
menor a mayor (por ejemplo 1, 2, 5, 10, 20, 50 y 100 euros), que se representan
mediante los valores vi
, con i ? {1, …, N} (en el caso anterior, N = 7) de manera
que de cada billete se tiene una cantidad finita, mayor o igual a cero, que se guarda
en ci (siguiendo con el ejemplo, c3 = 6 representaría que hay 6 billetes de 5 euros).
Se quiere pagar exactamente una cierta cantidad de dinero D, utilizando para ello
la menorcantidad de billetes posible. Se sabe que
n
D ? ?ci
vi
i?1
(es decir, que hay dinero suficiente para poder devolver la cantidad requerida) pero
puede que la cantidad exacta D no sea obtenible mediante los billetes disponibles.
Diseñar un algoritmo con la metodología de Programación Dinámica que
determine, teniendo como datos los valores ci
, vi y D,
? si la cantidad D puede devolverse exactamente o no, y
? en caso afirmativo, cuantos billetes de cada tipo forman la
descomposición óptima
(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)