OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
Acá vamos a hablar de un "problema típico", que puede verse en este [[http://codeforces.com/contest/864/problem/E|link]] a codeforces.

Básicamente, se tienen $n \leq 100$ ítems en peligro, cada ítem tiene un valor $v_i \leq 20$ que te da tener el ítem, un tiempo $t_i \leq 20$ que te lleva rescatar el ítem, y un momento $d_i \leq 2000$ 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).

El post se llama "planificar tareas optimamente" porque muchas veces el mismo problema aparece como una serie de tareas a realizar, que tienen un deadline (momento en el cual ya no se puede realizar), que llevan un determinado tiempo realizarla, y que nos da una determinada ganancia. Es un problema equivalente, pero tenía el link de codeforces a mano.


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. (Pensar qué pasa cuando tienen igual tiempo de desintegración.)


Ahora, vamos a resolver el problema con [[algoritmos-oia/programacion-dinamica|programación dinámica]]. 

Vamos a guardar en el estado $(i, j)$, cuál es el mejor valor que podemos obtener, mirando sólo a los primeros $i$ ítems, utilizando un tiempo $j$. Es importante notar que si bien el estado no demuestra por sí solo que hay que tener los ítems ordenados como los tenemos, podemos afirmar que está bien mirar "los primeros $i$ ítems" por lo que ya vimos antes, porque es un subproblema que tiene sentido ya que el orden es correcto.

**¿Cómo actualizamos el estado?**

Bueno, al mirar hasta el ítem $i+1$, podemos o bien haberlo rescatado recién, obteniendo su valor y consumiendo los últimos $t_{i+1}$ minutos, o no rescatarlo, sin consumir tiempo obteniendo como mejor valor el mejor valor hasta ese momento solamente con los primeros $i$ ítems:

$mejorValor_{i+1,j} = max(mejorValor_{i,j}, mejorValor_{i,j-t_{i+1}} + v_{i+1})$, siempre y cuando $j-t_{i+1}$ no sea negativo y el objeto no se haya desintegrado en el momento $j$.
Si en el momento $j$ el objeto se desintegró o necesito más de $j$ minutos para rescatarlo, entonces $mejorValor_{i+1,j}=mejorValor_{i,j}$

Como casi siempre en las dinámicas, lo difícil es pensar los estados y cómo ir de uno a otro, cómo actualizar los valores. Ahora que ya sabemos esos es simplemente dos fors y un if.

También lo que pide es que digamos qué items vamos a rescatar, en orden cronológico.

Para esto, lo que haremos será:
Entonces el momento tal que, mirando todos los ítems, acabamos de rescatar el último ítem que vamos a rescatar. Esto es el momento en el cual $mejorValor_{n,j}$ se maximiza.
Y partir de ahí, vamos a decir "bueno, ahora, mirando un ítem menos, tengo guardado el valor máximo que encontré más el valor del último ítem?", que es básicamente preguntar si en los fors actualizamos el valor del estado actual habiendo sumado el valor del i-ésimo ítem. Si lo hicimos, entonces como estamos mirando los valores máximos, es porque el i-ésimo ítem forma parte de nuestra solución, entonces lo agregamos a un vector de ítems rescatados.

Y finalmente imprimimos los ítems rescatados, en orden cronólogico, es decir, orden inverso a como los fuimos agregando (ver código)


==== Código ====

Se sugiere fuertemente intentar programarlo ustedes. Aunque no termine de salir, después ven el código de acá y ven cuánto les faltaba, pero al menos hacer un esfuerzo por pensar cómo programarían lo que se explica más arriba, que también ayuda a incorporar mejor las ideas.

...

...

Nota: Al final de la explicación, cuando hablamos de los estados de la dinámica, mencionábamos al ítem $i+1$, que en el código se obtiene como $items[i]$ ya que al estado de $i=0$ lo dejamos como "vacío" para poder tomar máximo siempre con el estado anterior y no andar haciendo "if(i>0)mejorValor[i-1]..." y meter ifs en el medio.

El código usa struct, de lo que pueden leer [[curso-cpp/struct|acá]].


<code cpp problema-E-seleccionar-items.cpp>

#include<bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0; i<(int)(n); i++)

struct item{
	int t, d, v, ind;
};

bool compItem(item a, item b){
	return a.d<b.d;
}

int main(){
    int n;
    cin>>n;
    vector<item> items;
    int termino=0;
    forn(i, n){
        item it;
        cin>>it.t>>it.d>>it.v;
        it.ind=i+1;
        termino=max(termino, it.d);
        items.push_back(it);
    }
    sort(items.begin(), items.end(), compItem);
    vector< vector<int> > mejorValor(n+1, vector<int>(termino+2, 0));
    forn(i, n){
        forn(j, termino+2){
            if(j-items[i].t>=0 && j<items[i].d){
                mejorValor[i+1][j]=mejorValor[i][j-items[i].t]+items[i].v;
            }
            mejorValor[i+1][j]=max(mejorValor[i][j], mejorValor[i+1][j]);
        }
    }
    int lastRescueMoment=0;
    forn(j, termino+2){
        if(mejorValor[n][j]>mejorValor[n][lastRescueMoment]){
            lastRescueMoment=j;
        }
    }
    cout<<mejorValor[n][lastRescueMoment]<<endl;
    vector<int> rescato;
    for(int i=n-1; i>=0; i--){
        if(lastRescueMoment>=items[i].t && mejorValor[i+1][lastRescueMoment]==mejorValor[i][lastRescueMoment-items[i].t]+items[i].v){
            lastRescueMoment-=items[i].t;
            rescato.push_back(items[i].ind);
        }
    }
    reverse(rescato.begin(), rescato.end());
    cout<<rescato.size()<<endl;
    forn(i, rescato.size())cout<<rescato[i]<<" ";
}

</code>


** Observaciones **

El hecho de primero ordenar, y luego usar como subproblema "los primeros $i$" es algo bastante típico en programación dinámica.

Algo que también sirve mucho mucho es **suponer que tenemos la solución óptima**, para ver por ejemplo el orden en el que podemos obtenerla, o si hay algo que podemos descartar.
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
