Tarea 8 de Diseño de Algoritmos

Trimestre 2012 Invierno
Entrega: 30 de marzo de 2012 a las 22:00.

Se tiene una banda por la que llegan N productos de vidrio a tu estación de trabajo en la que tienes M cajas de volumen V en la que guardarás algunos de estos productos. Cuando llega un producto a tu estación tienes dos opciones: lo guardas en la caja que tienes abierta o lo dejas que se caiga y se rompa. Una vez hecho esto tienes otras dos opciones: puedes cerrar la caja que tenías abierta y enviarla a la bodega o puedes seguir trabajando con la misma caja. Esto lo debes repetir mientras haya productos en la banda y cajas a tu disposición. Cada objeto tiene un cierto tamaño y cuando lo metes en una caja ocupas ese volumen. Si intentas meter un objeto que no cabe en la caja que tienes abierta entonces se rompen todos los objetos (tanto los de la caja actual, como los de las cajas previas y los que siguen en la banda). Observa que las decisiones las debes tomar conforme llegan los objetos a la banda.

Escribe un programa llamado vidrioZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que lleve a cabo esta tarea lo mejor posible (leyendo de la entrada estándar y escribiendo en la salida estándar). En este caso, tu objetivo es maximizar el volumen de los objetos que lograste guardar en las cajas.

Acción de tu programa
 Respuesta de mi programa
 Explicación
Inicio: Leer N, M y V
 Escribe N, M y V
 Tu programa lee la descripción general del problema
Ciclo: Lee el tamaño S del siguiente objeto
 Escribe el tamaño S del siguiente objeto
 Tu programa lee el tamaño del siguiente objeto
Decisión: Escribe G y C
(si todavía hay objetos y cajas, regresa al Ciclo)
 Lee G y C
 G = 1 significa que guardas el objeto en la caja actual y G = 0 significa que no lo guardas
C = 1 significa que cierras la caja y tomas la siguiente y C = 0 significa que no cierras la caja
Fin: Escribe T y A
 Lee T y A
 T es el número de objetos que nunca se procesaron
A es el número de cajas que no se utilizaron

Por ejemplo, si N = 3, M = 2 y V = 5 entonces la siguiente podría ser una interación valida entre tu programa y mi programa:

Acción de tu programa Respuesta de mi programa Explicación
Inicio: Leer N, M y V Escribe 3 2 5
 Esos son los valores de N, M y V
Lee S
 Escribe 4
 El primer objeto tiene tamaño 4
Escribe 1 1
 Lee G y C
 Tú decides guardar el objeto y cerrar la primera caja
Lee S
 Escribe 1
 El segundo objeto tiene tamaño 1
Escribe 1 0
 Lee G y C
 Tú decides guardar el objeto en la segunda caja y no cerrarla
Lee S
 Escribe 5
 El tercer objeto tiene tamaño 5
Escribe 0 0
 Lee G y C
 Como el objeto no cabe, decides no guardarlo y no cerrar la caja
Escribe 0 0
 Lee T y A
 Procesaste todos los objetos y usaste todas las cajas

Observa que el segundo objeto cabía en la primera caja, pero como ya la habías cerrado no puedes guardarlo allí. En este caso, guardaste un volumen total de 5 unidades (de un máximo de 10).