Este problema puede resolverse mediante programación dinámica.
Defina el mejor (i, j) = nivel máximo de diversión que se puede obtener de las primeras partes con una cantidad máxima de dinero.
Claramente, best (0, j) = best (i, 0) = 0 ya que necesita al menos algo de dinero y al menos alguna fiesta para divertirse. Difícil, pero así es la vida.
- ¿Cuáles son algunas de las preguntas de muestra de la búsqueda de jóvenes talentos en programación de computadoras realizada por Computer Society of India?
- ¿Qué es la verificación de enlaces de sitios web?
- ¿Por qué los proveedores vps no proporcionan estimaciones de CPU en sus comparaciones?
- ¿Qué es el caché obsoleto?
- ¿Cuál es la prueba intuitiva más simple del algoritmo de ruta más corta de Dijkstra?
Ahora, veamos la relación de recurrencia para mejor (i, j). Puede suceder que no puedas lograr más diversión con j cantidad de dinero que con j-1. En tal caso, best (i, j) = best (i, j). De lo contrario, eliges ir a la i-ésima fiesta o no. En el primer caso, la máxima diversión que puede tener es la mejor (i-1, j-fee [i]) + diversión [i] y en el segundo caso, es la mejor (i-1, j).
Tratando los casos límite cuidadosamente, obtenemos:
best (i, j) = max (best (i, j-1), best (i-1, j)) if j <fee [i]
best (i, j) = max (best (i, j-1), best (i-1, j), best (i-1, j-fee [i]) + fun [i]) de lo contrario.
best (n, k) te brinda la máxima diversión que puedes lograr de n fiestas con un presupuesto de k, y el valor más bajo de x de tal manera que best (n, k) = best (n, x) te da la cantidad mínima de dinero que necesita gastar para divertirse tanto.
