Page 80 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

alMaceNaMIeNto óptIMo eN cINtaS (optIMal Storage oN tapeS)

Existen n archivos que son almacenados en una cinta de tamaño L. Asociado con cada archivo i hay
un tamaño L, 1 ≤ i ≤ n. Todos los archivos pueden ser guardados en cinta iff la suma del tamaño
i
de los archivos es máximo L. Si los archivos son guardados en orden I = i , i , i , i ,..., i y el tiempo
1 1 2 3 n
requerido para guardar o recuperar el archivo i es T = ∑ L Si todo archivo es leído con la mis-
j j 1 ≤ k ≤ j i, k.
ma frecuencia, entonces el tiempo de referencia medio (TRM) es (1/n) ∑ t En el problema del
1 ≤ j ≤ n j.
almacenamiento óptimo, se requiere encontrar una permutación para n de tal forma que se minimice
el TRM. Minimizar TRM es equivalente a minimizar D(I) = ∑ I Por ejemplo:
∑1 ≤ k ≤ j 1 ≤ k ≤ j i, k.
N = 3 (I , I , I ) = (5, 10, 3).
1 2 3
Existen N! = 6 posibles ordenaciones.

El orden óptimo es (3, 1, 2). En este algoritmo, el método greedy requiere que los archivos sean
almacenados en forma creciente Esta ordenación puede realizarse por medio de un algoritmo de
ordenación como merge sort, por lo que requiere O (n log n).

el proBleMa de la MocHIla (kNapSack proBleM)

Se tienen n objetos y una mochila. El objeto i tiene un peso W y la mochila tiene una capacidad M. Si
i
una fracción X, 0 ≤ Xi ≤ 1 del objeto i se introduce, se tendrá una ganancia P X. El objetivo es llenar
i i i
la mochila de tal forma que maximice la ganancia. El problema es:

74