Herramientas de usuario
¡Esta es una revisión vieja del documento!
Acá vamos a hablar de un “problema típico”, que puede verse en este link a codeforces.
Básicamente, se tienen $n \leq 1000$ ítems en peligro, cada ítem tiene un valor $v_i$ que te da tener el ítem, un tiempo $t_i$ que te lleva rescatar el ítem, y un momento $d_i$ a partir del cual el ítem ya es imposible de rescatar (se desintegra). Querés decidir qué ítems rescatar de manera de maximizar el valor total (la suma de los valores de los ítems rescatados).
Se recomienda pensar el problema antes de seguir a ver la respuesta. Pregunta “pista importante”: Dados dos ítems, qué nos indica en qué orden vamos a rescatarlos?
La respuesta a esa pregunta es la observación clave del problema: Supongamos que sabemos que la solución óptima. Y nos preguntamos, tiene sentido rescatar primero a un ítem que se desintegra primero? Supongamos que rescatamos a dos ítems, $a$ y $b$, en ese orden, uno después del otro, tales que $d_a > d_b$, es decir el primer ítem se desintegra después que el segundo. Entonces, si al ítem $a$ lo vamos a rescatar en el momento $x_a$, al $b$ lo vamos a rescatar en el momento $x_b=x_a+t_a$. Como estamos en la solución óptima, entonces sabemos que $x_a+t_a<d_a$, y $x_b+t_b=x_a+t_a+t_b<d_b$.
Y si los rescatáramos al revés, al $b$ lo iríamos a rescatar en el momento $x_a$, terminando en $x_a+t_b$, y sabemos que $x_a+t_b<x_a+t_b+t_a<d_b$, por lo que podemos rescatarlo, y al ítem $a$ lo terminamos de rescatar en $x_a+t_a+t_b<d_b<d_a$ por hipótesis. Entonces, tenemos que dados ítems que queremos rescatar, si podemos, seguro podemos en orden creciente de los valores $d_i$.
Dada esa importantísima observación, proseguimos. Comenzamos obviamente ordenando los ítems según sus valores de desintegración.
Herramientas de la página
