Tarea 5 de Diseño de Algoritmos
Trimestre 2007 Primavera
Entrega: 9 de julio de 2007 a las 22:00.
Problema 1: Considere el problema de
asignación de intervalos visto en clase con la
modificación de que cada intervalo solicitado tiene un costo:
Sea L la
longitud del intervalo disponible, sea N el número de intervalos
solicitados y para cada 1 <= I <= N sean AI, BI
y CI el inicio, fin y precio del intervalo solicitado,
respectivamente. Diseñe una heurística que seleccione
algunos de los intervalos solicitados de modo que no se traslapen y que
la suma de los costos sea tan grande como sea posible. Por ejemplo, si
L = 4, N = 3, el primer intervalo va de A1 = 2 a B1
= 4 y cuesta C1 =
2, el segundo intervalo va de A2 = 0 a B2 = 1 y
cuesta C2 = 4, el tercer intervalo va de A3 = 1 a
B3 = 3 y cuesta C3 = 3 entonces lo mejor que se
puede hacer es escoger los intervalos 2 y 3 para una suma de costos de
7. Escriba un programa en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado costosZZ (donde ZZ es una clave de dos
dígitos asignada por el profesor) basado en su algoritmo
que acepte como entrada dos números enteros L y N y tres
vectores A, B y C de N enteros cada uno y que
escriba como salida la cantidad K de intervalos seleccionados, los K
intervalos seleccionados y la suma de los costos de esos K intervalos.
De nuevo, si la entrada
fuera
4
3
2 4 2
0 1 4
1 3 3
entonces la salida podría ser
2
2 3
7
Puede suponer que 0 < L < 1,000, que 0 < N <
1,000,000, que 0 <= AI < BI <= L y que 0
< CI < 1000 para toda 1 <= I <= N.
Problema 2: Considere el
problema de
asignación de intervalos visto en clase con la
modificación de que se tienen dos intervalos idénticos
disponibles: Sea L la
longitud del intervalo disponible, sea N el número de intervalos
solicitados y para cada 1 <= I <= N sean AI y BI
el inicio y el fin del intervalo solicitado,
respectivamente. Diseñe una heurística que asigne
algunos de los intervalos solicitados a cada uno de los dos intervalos
disponibles de modo que no se traslapen y que
la cantidad de intervalos asignados sea tan grande como sea posible.
Por ejemplo, si
L = 6, N = 5, el primer intervalo va de A1 = 0 a B1
= 3, el segundo intervalo va de A2 = 4 a B2 = 6,
el tercer intervalo va de A3 = 2 a B3 = 4, el
cuarto intervalo va de A4 = 1 a B4 = 4, el quinto
intervalo va de A5 = 3 a B5 = 6 entonces lo
mejor que se puede hacer es asignar dos intervalos (digamos el primero
y el quinto) al primer intervalo disponible y asignar otros dos
intervalos (digamos el segundo y el cuarto) al segundo intervalo
disponible para un total de 4 intervalos asignados. Escriba un programa
en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado doblesZZ (donde ZZ
es una clave de dos
dígitos asignada por el profesor) basado en su algoritmo
que acepte como entrada dos números enteros L y N y dos vectores
A y B de N enteros cada uno y que
escriba como salida las cantidades K1 y K2 de
intervalos seleccionados para cada intervalo disponible, los K1
intervalos seleccionados para el primer intervalo y los K2
intervalos seleccionados para el segundo intervalo.
De nuevo, si la entrada
fuera
6 5
0 4 2 1 3
3 6 4 4 6
entonces la salida podría ser
2
2
1 5
2 4
Puede suponer que 0 < L < 1,000, que 0 < N <
1,000,000, y que 0 <= AI < BI <= L para
toda 1 <= I <= N.
Nota: Sus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado.