Trimestre 2012 Otoño
Entrega: 23 de noviembre de 2012 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 chicoZZ
(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 volumen a
menor
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 5, 4, 3, 1, 2.
Problema 2: Escribe un programa llamado caroZZ
(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 costo a mayor
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 3, 1, 5, 2, 4.
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
0 1 0 0 1
10
1 1 1 0 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.