Algoritmica

TEORÍA DE ALGORITMOS
RELACIÓN DE PROBLEMAS
TEMA 4. ALGORIMOS GREEDY
1. Se tiene un barco de mercancías cuya capacidad de carga es de k toneladas y un conjunto de
contenedores c1,...., cn, cuyospesos respectivos (expresados también en toneladas) son p1,
...., pn. Se sabe que la capacidad del barco es inferior a la suma total de los pesos de los
contenedores.
a) Diseñar un algoritmo quemaximice el número de contenedores cargados.
b) Diseñar un algoritmo para maximizar el número de toneladas cargado.
Indicar las técnicas de diseño utilizadas en ambos problemas y analizar sucomplejidad.
2. Sean n programas P1, ..., Pn que hay que almacenar en un disco. El programa Pi requiere Si
Kilo bites de espacio y la capacidad del disco es D Kilo bites, donde D < ∑Si. Resolver lassiguientes cuestiones:
•
•

Se desea maximizar el número de programas almacenados en el disco. Construir un
algoritmo greedy para resolver el problema (existe un algoritmo que da una solución
óptima).Se desea utilizar la mayor capacidad posible del disco. Demostrar que podemos utilizar
un algoritmo greedy que seleccione los programas por orden no creciente de sí para
obtener la solución exacta odar un contraejemplo en caso contrario.

3. Tenemos que ejecutar un conjunto de n tareas, cada una de las cuales requiere un tiempo
unitario. En un instante T = 1, 2, ... podemos ejecutarúnicamente una tarea. La tarea i
produce unos beneficios gi (gi > 0) sólo en el caso en el que sea ejecutada en un instante
anterior o igual a di. Utilizando la técnica greedy encontrar un algoritmo que nospermita
seleccionar el conjunto de tareas a realizar de forma que nos aseguremos que tenemos la
mayor ganancia posible.
Resolver el problema utilizando la siguiente instancia:
i
1
2
3
4
gi50
10
15
30
di
2
1
2
1
4. Consideremos el grafo no-dirigido G = (V, E). Un conjunto de nodos U se dice un
cubrimiento de G si U es un subconjunto de V tal que cada arista en E es incidente...