D - Un tren con dos destinos
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits:
(details)
En un almacén de suministros se tiene un tren listo para partir con todos sus vagones llenos de materias primas. Estas han de ser entregadas en dos fábricas ubicadas en distintos lugares del país. El tren normalmente va con todos los vagones hasta un punto equidistante de ambas fábricas donde deja su carga y luego vuelve al almacén. En ese punto los vagones se dividen en dos conjuntos y dos trenes más pequeños se los llevan a su destino final. El problema ahora es que al ser más pequeños este par de trenes, entonces es posible que no todos los vagones puedan ser llevados en un viaje a las fábricas desde el punto donde los dejó el primer tren, lo que termina generando una situación incómoda. Es fácil entender que si se deja algún vagón esperando por un viaje futuro, entonces se entorpecería el tráfico en ese punto del recorrido y además los vagones pudieran resultar blanco de potenciales ilegalidades.
El objetivo en este problema consiste en escoger la mayor cantidad de vagones para trasladar en el primer tren, de forma tal que sea posible dividirlo en dos conjuntos que puedan ser llevados cada uno por un tren pequeño. Como las dos industrias son de igual importancia los dos conjuntos deben tener la misma cantidad de vagones, aunque tengan peso total distinto (por ejemplo si tienen distintos materiales dentro). Dado que no se tiene mucho tiempo para escoger los vagones al inicio entonces los que se hace es separar uno de los vagones del resto, de esta forma el tren solo se lleva los vagones que están antes del que es separado y el resto se queda en el almacén bien vigilado.