Programación dinámica/Programas en disco

Descripción del problema

El 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

El 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:
1. No lo incluimos, y seguimos probando con el resto de programas, o
2. 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

Fun 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

Se 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:

Matriz generada
	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
1	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
2	10	10	10	10	10	15	15	15	15	15	15	15	15	15	15	25	25	25	25	25	25
3	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

Martí, Narciso; Verdejo, Alberto; Ortega Yolanda. Estructuras de datos y métodos algoritmicos: ejercicios resueltos (2003). Madrid: Prentice Hall.