Herramientas de usuario
algoritmos-oia:problemas-generales:planificar-tareas-optimamente
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:problemas-generales:planificar-tareas-optimamente [2018/01/03 02:00] sebach |
algoritmos-oia:problemas-generales:planificar-tareas-optimamente [2018/02/07 07:14] (actual) sebach [Código] |
||
|---|---|---|---|
| Línea 31: | Línea 31: | ||
| $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$. | $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 (más o igual en realidad según el problema), entonces $mejorValor_{i+1,j}=mejorValor_{i,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. | 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. | ||
| Línea 53: | Línea 53: | ||
| 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. | 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á]]. | ||
| Línea 77: | Línea 79: | ||
| int termino=0; | int termino=0; | ||
| forn(i, n){ | forn(i, n){ | ||
| - | item it; | + | item it; |
| - | cin>>it.t>>it.d>>it.v; | + | cin>>it.t>>it.d>>it.v; |
| - | it.ind=i+1; | + | it.ind=i+1; |
| - | termino=max(termino, it.d); | + | termino=max(termino, it.d); |
| - | items.push_back(it); | + | items.push_back(it); |
| - | } | + | } |
| - | sort(items.begin(), items.end(), compItem); | + | sort(items.begin(), items.end(), compItem); |
| - | vector< vector<int> > mejorValor(n+1, vector<int>(termino+2, 0)); | + | vector< vector<int> > mejorValor(n+1, vector<int>(termino+2, 0)); |
| - | forn(i, n){ | + | forn(i, n){ |
| - | forn(j, termino+2){ | + | forn(j, termino+2){ |
| - | if(j-items[i].t>=0 && j<items[i].d){ | + | if(j-items[i].t>=0 && j<items[i].d){ |
| - | mejorValor[i+1][j]=max(mejorValor[i+1][j], mejorValor[i][j-items[i].t]+items[i].v); | + | 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]); | + | mejorValor[i+1][j]=max(mejorValor[i][j], mejorValor[i+1][j]); |
| - | } | + | } |
| - | } | + | } |
| - | int lastRescueMoment=0; | + | int lastRescueMoment=0; |
| - | forn(j, termino+2){ | + | forn(j, termino+2){ |
| - | if(mejorValor[n][j]>mejorValor[n][lastRescueMoment]){ | + | if(mejorValor[n][j]>mejorValor[n][lastRescueMoment]){ |
| - | lastRescueMoment=j; | + | lastRescueMoment=j; |
| - | } | + | } |
| - | } | + | } |
| - | cout<<mejorValor[n][lastRescueMoment]<<endl; | + | cout<<mejorValor[n][lastRescueMoment]<<endl; |
| - | vector<int> rescato; | + | vector<int> rescato; |
| - | for(int i=n-1; i>=0; i--){ | + | 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){ | + | if(lastRescueMoment>=items[i].t && mejorValor[i+1][lastRescueMoment]==mejorValor[i][lastRescueMoment-items[i].t]+items[i].v){ |
| - | lastRescueMoment-=items[i].t; | + | lastRescueMoment-=items[i].t; |
| - | rescato.push_back(items[i].ind); | + | rescato.push_back(items[i].ind); |
| - | } | + | } |
| - | } | + | } |
| - | reverse(rescato.begin(), rescato.end()); | + | reverse(rescato.begin(), rescato.end()); |
| - | cout<<rescato.size()<<endl; | + | cout<<rescato.size()<<endl; |
| - | forn(i, rescato.size())cout<<rescato[i]<<" "; | + | forn(i, rescato.size())cout<<rescato[i]<<" "; |
| } | } | ||
| - | |||
| </code> | </code> | ||
algoritmos-oia/problemas-generales/planificar-tareas-optimamente.1514944837.txt.gz · Última modificación: 2018/01/03 02:00 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
