# Ejercicio 6 practica 1 algo3
## a)
$cc(B, c) =
\begin{cases}
0 & \text{si } c = 0 \\
b_n & \text{si } b_n = c \\
\min(cc(B \setminus \{b_n\}, c), cc(B \setminus \{b_n\}, c - b_n) + 1) & \text{si } b_n < c
\end{cases}$
## b)
```python
def cc(B, c):
# Caso base: Si c es 0, hemos alcanzado el objetivo exactamente.
if c == 0:
return (0, 0) # No exceso, 0 billetes usados.
# Si ya no hay billetes para considerar y no hemos alcanzado el objetivo.
if not B and c > 0:
return None # Imposible alcanzar c con los billetes dados.
# Consideramos b el primer billete en B.
b = B[0]
# Caso: El billete actual iguala exactamente a c.
if b == c:
return (0, 1) # No exceso, 1 billete usado.
# Caso: el billete actual es mayor que c, hay que pasar al siguiente
if b > c:
return cc(B[1:],c)
# Probamos dos opciones: no usar el billete actual y usar el billete actual.
# No usar b
opcion1= cc(B[1:],c)
# Usar b y sumar 1 al resultado de esta opción
opcion2 = cc(B[1:],c-b)
if opcion2 is not None:
opcion2 = (opcion2[0], 1 + opcion2[1])
# elegir la opción que minimiza la cantidad de billetes usadsos.
if opcion1 is None and opcion2 is not None:
return opcion2
elif opcion2 is None and opcion1 is not None:
return opcion1
elif opcion1 is not None and opcion2 is not None:
## Revisamos el min
return min(opcion1, opcion2)
else:
return None
```
#
- Al ser un algoritmo de backtracking e ir descartando posibilidades este algoritmo en peor caso va a tener una complejidad exponencial $O(2^n)$.
## c)
- Claramente el algoritmo convive con solapamiento de subproblemas al realizar múltiples llamados recrusivos que resuelven los mismos subproblemas cantidad de veces.
- Para solucionar esto hay que utilizar programación dinamica para reducir drasticamente la complejidad temporal a $O(n \times c)$ siendo $n$ el número de billetes y $c$ la cantidad a llegar.
- Para reformular la función recursiva $cc$ hay que agregar memoización.
#
$cc'(B, i, j) =
\begin{cases}
0 & \text{si } j = 0 \\
\text{None} & \text{si } i = 0 \text{ y } j > 0 \\
b_i & \text{si } b_i = j \\
cc'(B, i-1, j) & \text{si } b_i > j \\
\min(cc'(B, i-1, j), (1 + \text{exceso}, 1 + \text{billetes})) & \text{donde } (exceso, billetes) = cc'(B, i-1, j - b_i) & \text{si } b_i < j
\end{cases}$
- Se llama con el subcjto B desde el 1er elemeneto hasta el i-esimo con la suma objetivo j.
- La última llamada recursiva representaría la memoización donde lo almacena en variable de exceso y billetes. No sé sí está bien del todo.
## d-e-f)
```python
memo = {}
def cc(B, c):
# Verificamos si y ya está en memoria
if (len(B),c) in memo:
return memo[(len(B),c)]
# Caso base: Si c es 0, hemos alcanzado el objetivo exactamente.
if c == 0:
return (0, 0) # No exceso, 0 billetes usados.
# Si ya no hay billetes para considerar y no hemos alcanzado el objetivo.
if not B and c > 0:
return None # Imposible alcanzar c con los billetes dados.
# Consideramos b el primer billete en B.
b = B[0]
# Caso: El billete actual iguala exactamente a c.
if b == c:
memo[(len(B), c)] = (0, 1) # No exceso, 1 billete usado.
return (0,1)
# Caso: el billete actual es mayor que c, hay que pasar al siguiente
if b > c:
result = cc(B[1:],c)
memo[(len(B),c)] = result
return result
# Probamos dos opciones: no usar el billete actual y usar el billete actual.
# No usar b
opcion1= cc(B[1:],c)
# Usar b y sumar 1 al resultado de esta opción
opcion2 = cc(B[1:],c-b)
if opcion2 is not None:
opcion2 = (opcion2[0], 1 + opcion2[1])
# elegir la opción que minimiza la cantidad de billetes usadsos.
result = None
if opcion1 is None and opcion2 is not None:
result = opcion2
elif opcion2 is None and opcion1 is not None:
result = opcion1
elif opcion1 is not None and opcion2 is not None:
## Revisamos el min
result = min(opcion1, opcion2)
else:
result = None
memo[((len(B),c))] = result
# Almacenar resultado en memoria antes de retornarlo
return result
```
- La clave para el diccionario de memoización es una tupla que contiene la longitud de la lista B y el total c. La longitud B se utiliza como forma de representar el estado actual de B.