Trimestre 2010 Otoño
Entrega: 29 de noviembre de 2010 a las 22:00.
En esta tarea programarán dos heurísticas glotonas para
el problema de la mochila con costos
que se define como sigue: Sea N un entero positivo y considere que
tiene N objetos (numerados del 1 al N) que ocupan un cierto volumen y
tienen un cierto costo (para 1 <= I <= N, el objeto I tiene
volumen VI y costo CI). Sea M un entero positivo
y considere que tiene una mochila de capacidad M. Se desea escoger
algunos de los objetos para colocarlos dentro de la mochila maximizando
el costo total de los objetos seleccionados.
Por ejemplo si N = 5, M = 10, V = (3, 1, 4, 5, 9) y C = (2, 7, 1, 8, 3)
entonces lo mejor que se puede hacer es tomar los objetos 1, 2 y 4 con
un volumen total de 3+1+5 = 9 y un costo total de 2+7+8 = 17. Observe
que no necesariamente se llena la mochila en la mejor solución
posible.
Problema
1: Escribe un programa llamado grandeZZ
(donde ZZ es una clave de
dos
dígitos asignada por el profesor) que implemente la siguiente
heurística glotona: Ordena los objetos de menor volumen a mayor
volumen y, en ese orden, colócalos en la mochila si es que
todavía caben. En nuestro ejemplo, esto significa que los
objetos se deberán considerar en el orden 2, 1, 3, 4, 5.
Problema 2: Escribe un programa llamado baratoZZ
(donde ZZ
es una clave de
dos
dígitos asignada por el profesor) que implemente la siguiente
heurística glotona: Ordena los objetos de mayor costo a menor
costo
y, en ese orden, colócalos en la mochila si es que
todavía caben. En nuestro ejemplo, esto significa que los
objetos se deberán considerar en el orden 4, 2, 5, 1, 3.
La entrada para ambos programas serán dos enteros N y M seguidos
de un renglón con N enteros V1, V2, ..., VN
seguido de otro renglón con N enteros C1, C2,
...,
CN. Puedes suponer que 1 <= N <= 1,000,000, que 1
<= M <= 1,000,000,000 y para toda 1 <= I <= N que 1 <= VI
<= 1,000,000 y 1 <= CI <= 1,000,000. También
puedes suponer que todos los volúmenes serán distintos y
que todos los costos serán distintos (de esta forma no
podrá haber empates durante la ejecución del algoritmo).
La salida para ambos programas será un entero T (el costo total
de los objetos seleccionados) seguido de un renglón con N
enteros X1, X2, ..., XN que indican si
el objeto I fué seleccionado (XI = 1) o no (XI
= 0). Observe que en ambos casos la salida será correcta (es
decir, los objetos seleccionados cabrán en la mochila) pero tal
vez no sea la óptima.
Ejemplo de
entrada
Ejemplo de
salida (Problema 1)
Ejemplo de
salida (Problema 2)
5 10
3 1 4 5 9
2 7 1 8 3
10
1 1 1 0 0
17
1 1 0 1 0
Notas: Tus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado. El
tiempo de ejecución de tus algoritmos será considerado
como parte de la evaluación.