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 Última revisión Ambos lados, revisión siguiente | ||
|
algoritmos-oia:problemas-generales:planificar-tareas-optimamente [2018/01/03 01:59] sebach [Código] |
algoritmos-oia:problemas-generales:planificar-tareas-optimamente [2018/01/03 02:04] sebach [Código] |
||
|---|---|---|---|
| Línea 22: | Línea 22: | ||
| - | 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. | + | Ahora, vamos a resolver el problema con [[algoritmos-oia/programacion-dinamica|programación dinámica]]. |
| - | ¿Cómo actualizamos el estado? | + | 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: | 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$. | $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 51: | 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 86: | Línea 90: | ||
| 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]); | ||
| Línea 109: | Línea 113: | ||
| forn(i, rescato.size())cout<<rescato[i]<<" "; | forn(i, rescato.size())cout<<rescato[i]<<" "; | ||
| } | } | ||
| - | |||
| </code> | </code> | ||
algoritmos-oia/problemas-generales/planificar-tareas-optimamente.txt · Última modificación: 2018/02/07 07:14 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
