Ejercicios resueltos de Programación dinámica

Question 1

La sucesión de Fibonacci se define como fib(n) = fib(n − 1) + fib(n − 2), con fib(0) = 0 y fib(1) = 1. Programada tal cual, ¿cuántas llamadas hace para calcular fib(6)? ¿Y con memoización?

Accepted Answer

Escrita tal cual, la función se llama a sí misma dos veces y las dos ramas repiten trabajo: fib(4) se calcula dentro de fib(6) y otra vez, completo, dentro de fib(5). Para contar el árbol de llamadas se usa C(n) = 1 + C(n − 1) + C(n − 2), donde ese 1 es la llamada actual, con C(0) = C(1) = 1 porque son casos base y no llaman a nadie. C(2) = 1 + 1 + 1 = 3. C(3) = 1 + 3 + 1 = 5. C(4) = 1 + 5 + 3 = 9. C(5) = 1 + 9 + 5 = 15. C(6) = 1 + 15 + 9 = 25. De esas 25 llamadas, valores distintos solo hay 7: de fib(0) a fib(6). Todo lo demás es trabajo repetido, y crece de forma exponencial: fib(40) pasa de 300 millones de llamadas. La memoización guarda cada resultado en un diccionario apenas se calcula y, antes de calcular cualquier cosa, revisa si ya está guardado. Con eso cada valor se calcula una sola vez: 7 cálculos para fib(6) y 41 para fib(40). El costo baja de O(2ⁿ) a O(n). Respuesta: Sin memoización son 25 llamadas para obtener fib(6) = 8. Con memoización se calculan solo los 7 valores distintos y el algoritmo pasa de exponencial a lineal.

Question 2

Un vendedor va a una feria en Bogotá y solo puede cargar 10 kg. Tiene café (6 kg, $42.000 de ganancia), queso (5 kg, $32.000) y panela (5 kg, $28.000). No puede partir los productos. ¿Qué lleva para ganar lo máximo?

Accepted Answer

Es una mochila 0/1: cada producto se lleva entero o no se lleva. Por eso hay que evaluar combinaciones y no basta con un criterio de «lo mejor primero». La recurrencia de la programación dinámica es M(i, c) = el mejor valor usando los primeros i productos con c kilos disponibles = el máximo entre M(i − 1, c), que es no llevar el producto i, y valorᵢ + M(i − 1, c − pesoᵢ), que es llevarlo si cabe. Con el café solo: con menos de 6 kg disponibles no cabe y el mejor valor es $0; con 6 kg o más el mejor valor es $42.000. Se agrega el queso (5 kg, $32.000). Con 5 kg disponibles el mejor pasa a ser $32.000, porque el café no cabe. Con 10 kg: no llevar el queso deja $42.000; llevarlo da 32.000 + M(solo café, 10 − 5 = 5 kg) = 32.000 + 0 = $32.000. Gana la opción de $42.000. Se agrega la panela (5 kg, $28.000). Con 10 kg: no llevarla deja los $42.000 del paso anterior; llevarla da 28.000 + M(café y queso, 10 − 5 = 5 kg), y en el paso anterior quedó anotado que con 5 kg lo mejor era el queso solo, $32.000. Llevarla da entonces 28.000 + 32.000 = $60.000, que supera los $42.000. El óptimo es queso + panela, 10 kg exactos. Respuesta: Lleva queso y panela: 10 kg exactos y $60.000 de ganancia. Llevar el café deja la carga en 6 kg y solo $42.000.

Programación dinámica