Creo que tiene la misma lógica que esto:
Problema de la monedaEl denominado "problema de la moneda" es el siguiente: dados diferentes tipos de monedas, cada uno con un valor diferente, y una cantidad C, ¿cuál es el menor número de monedas necesarias para devolver el cambio C?
Para las monedas del sistema monetario del euro existe una estrategia básica para resolver el problema:
Coge una moneda con el valor V más grande tal que V <= C
Repite desde 1 con el valor C - V hasta que C = 0
Sin embargo, esta estrategia no funciona para valores aleatorios de las monedas. Por ejemplo, si las monedas tienen valores 1, 4 y 6, el número mínimo de monedas para hacer un cambio de 8 es 2 monedas de 4 (cogiendo una moneda de 6 necesitamos como mínimo 3 monedas en total).
En general, para resolver el problema de la moneda tenemos que probar todas las posibles combinaciones de coger monedas. Para la cantidad C, las posibilidades son: coger una moneda del primer tipo, coger una moneda del segundo tipo, etc. En cada caso se genera un subproblema del mismo tipo por resolver. Por ejemplo, si cogemos una moneda de valor 1, recursivamente tenemos que encontrar la mejor manera de devolver el cambio C-1, y sumarle 1 para obtener una posible solución para C. La solución para C es la mejor entre todas estas posibles maneras de coger la primera moneda.
Si denominamos A(C) el subproblema para la cantidad C, una definición resursiva para el problema es:
A(0) = 0 (si la cantidad es 0 no necesitamos ninguna moneda)
A(C) = min(1 + A(C-m_1), 1 + A(C-m_2), ..., 1 + A(C-m_k))
donde k es el número total de monedas y m_i es el valor de la moneda i. Ahora podemos escribir una solución basada en la programación dinámica:
int M[3] = {1, 4, 6}; // tipos de moneda diferentes
int A[100001];
A[0] = 0;
for (int C = 1; C <= 100000; ++C) {
A[C] = 1000000000; // número grande para empezar
for (int i = 0; i < 3; ++i)
if (M[i] <= C && 1 + A[C-M[i]] < A[C])
A[C] = 1 + A[C-M[i]];
}
Después del bucle el array A contendrá el resultado para cada C en el rango [0, 100000].
engel lex, me das una mano para calcular la formula de la función del principio? Por que esto me preguntaron en el final de Estructura de Datos, aprobé con 6 pero no supe hacer ese ejercicio.
Había que hacer la fórmula y luego programarlo en "programación dinámica"
Agradezco cualquier respuesta.