[ Foro de C++ ]

Resolver un ejercicios

23-May-2019 02:48
Invitado (Sebastian)
0 Respuestas

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




Si ya eres usuario del sistema, puedes contestar desde tu cuenta y así ganar prestigio.

Si sólo eres un visitante, puedes optar por...