Programación dinámica/Programas en disco
Descripción del problema
editarEl problema de los Programas en disco consiste en: Se consideran n programas P1, P2,... , Pn que se almacenan en un disco. El programa "Pi" requiere "Si" megabytes de espacio de disco, y la capacidad del disco es D megabytes.
Suponiendo que los programas no pueden fraccionarse se desea maximizar el espacio utilizado del disco.
Solución usando Programación Dinámica
editarEl problema consiste en maximizar Σ Pi*Si (iε{1..n}) con la restricción Σ Pi*Si <= D (iε{1..n}), donde Pi ε {0,1} dice si se ha seleccionado (1) o no (0) el programa i.
Para resolver el problema se define una función
espacio(i, j) = máximo espacio que podemos ocupar en un disco de capacidad máxima j considerando los programas del 1 al i.
Se calcula esta función mediante una recurrencia que va a tener en cuenta las distintas posibilidades. Se considera primero el programa i. Habrá dos posibilidades:
- Que no se pueda meter el programa i porque su tamaño supera la capacidad que todavía se puede añadir al disco, en cuyo caso se tendrá que llenar el disco con los objetos restantes, del 1 al i-1.
- Que sí se pueda meter, en cuyo caso se plantean dos opciones:
- No lo incluimos, y seguimos probando con el resto de programas, o
- Sí lo incluimos, obteniendo un espacio Si, y llenamos el resto del disco(j - Si) con el resto de los programas.
Como se está tratando de maximizar el espacio utilizado en el disco, se elegirá la posibilidad de mayor valor.
Se puede definir de forma recursiva la función espacio al cumplirse el principio de optimalidad, de forma que basta considerar solamente soluciones óptimas para los subproblemas. Así pues se tiene la siguiente recurrencia (ei es el espacio que ocupa el programa i):
espacio(i, j) = espacio(i – 1, j) si ei > j espacio(i, j) = máx{espacio(i – 1, j), espacio(i – 1, j - ei) + ei} si ei <= j
donde 1 <= i <= n y 1 <= j <= D, y la recursión está bien fundada porque uno o los dos argumentos decrecen estrictamente.
Los casos básicos se presentan, bien cuando no se tiene programas que considerar, o bien cuando no queda espacio en el disco. En ambos casos el único espacio posible es 0:
espacio(0, j) = 0 1 <= j <= D espacio(i, 0) = 0 0 <= i <= n
Se van a calcular los valores de espacio(i, j) con ayuda de una tabla espacio[0..n, 0..M]. Para calcular la posición espacio[i, j] se necesita haber calculado dos posiciones de la fila anterior (i - 1). Se puede recorrer la matriz por filas de arriba abajo y cada fila de izquierda a derecha (o de derecha a izquierda). Al terminar de rellenar la matriz, espacio[n, D] contendrá el espacio ocupado de la solución óptima.
Implementación en pseudocódigo
editarFun maximizar_espacio_ocupado(prog[1..n] de nat, D: nat) dev <ocup:nat, cuales[1..n] de 0..1> Var disco[0..n, 0..D] de nat {Inicialización de la matriz} para i = 0 hasta n hacer disco[i, 0] = 0 fpara para j = 1 hasta D hacer disco[0, j] = 0 fpara {Rellenar la matriz} para i = 1 hasta n hacer para j = 1 hasta D hacer si prog[i] > j entonces disco[i, j] = disco[i - 1, j] si no disco[i, j] = máx{disco[i - 1, j], disco[i - 1, j – prog[i]] + prog[i]} fsi fpara fpara ocup = disco[n, D]; {solución del problema} {Cálculo de los programas que forman parte de la solución} resto = D; para i = n hasta 1 paso -1 hacer si espacio[i, resto] = espacio[i – 1, resto] entonces {no se coge el programa i} cuales[i] = 0 si no cuales[i] := 1; resto := resto – prog[i] fsi fpara ffun
Ejemplo
editarSe tiene un disco con una capacidad máxima D = 30 megabytes y los siguientes programas:
P1 = 10 megabytes
P2 = 15 megabytes
P3 = 20 megabytes
Siguiendo el método descrito se obtendría una matriz con los siguientes valores:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 25 | 25 | 25 | 25 | 25 | 25 |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 15 | 15 | 15 | 15 | 15 | 20 | 20 | 20 | 20 | 20 | 25 | 25 | 25 | 25 | 25 | 30 |
Cada celda [i,j] representa la cantidad de espacio que se puede ocupar en un disco de capacidad j usando los programas 1...i. De este modo, la solución al problema se encuentra en la casilla [3,30], cuyo valor es 30. Efectivamente, se comprueba que se puede llenar el disco con los programas P1 y P3.
Bibliografía
editarMartí, Narciso; Verdejo, Alberto; Ortega Yolanda. Estructuras de datos y métodos algoritmicos: ejercicios resueltos (2003). Madrid: Prentice Hall.