Page 45 - revista 2019

Revista de la Facultad de Ingeniería, Año 6, Número 1

Figura 3: Un ejemplo de una sección del PDF a producir. Para lograr un margen
derecho parejo puede ser necesario agregar espacio en blanco en cada fila
(ensanchando los campos de la misma) pero se quiere minimizar tales agregados, por
estética.
Podemos considerar un ejemplo. Digamos que hay cinco campos, de anchos 7, 2, 5,
3, y 6, y queremos disponerlos en filas de ancho 10. (Véase la figura 4.)

Figura 4: Un caso práctico: tenemos cinco campos a organizar en filas de ancho 10.
Las soluciones óptimas requieren tres filas, pero hay varias posibilidades: ¿cuál es la
mejor?
Analizando los tres casos, en todos debemos agregar 7 espacios en blanco, pero
¿cuál es la solución más estética? Una idea es definir un “costo por fila”, en función
del espacio extra, y minimizar la suma total de costos. El cliente preferiría más costos
chicos y menos costos grandes, por lo que definir el costo de una fila como “(espacio
agregado)2” sirve: si hay que agregar dos espacios en blanco en dos filas, es
preferible agregar uno por fila (costo 12+12=2), que dos en una y ninguno en la otra
(costo 22+02=4).
Con esta definición (que nos da una meta a buscar para el algoritmo) tenemos que la
primera solución de la figura 4 tiene un costo de 21 (12+22+42), la segunda de 25
(32+02+42) y la tercera de 19 (32+32+12): ésta es la preferible.

Ahora, ¿cómo podemos llegar a esta solución? Asumamos que tenemos los bloques
numerados, en secuencia, con ancho w[i], y ancho máximo por fila MW. Hallar la
solución de modo iterativo es difícil, pero recursivamente se puede. Queremos el
costo de poner en una misma fila todos los campos desde una posición p hasta otra
posición q, ¿cuál es éste?

Si los campos desde p hasta q caben juntos, es simple: calculemos el espacio
sobrante, y el costo será el cuadrado del número calculado

Si no caben juntos, dividámoslos en dos partes; calculemos el costo de cada una;
sumémoslos; y quedémonos con la partición de menor suma.

Un algoritmo apropiado para encontrar el costo óptimo se muestra en el listado 3.
(Hemos ignorado, por claridad, recordar dónde cortar cada línea.)

44