Tarea 7 de Diseño de Algoritmos

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.