Resolviendo el #TuentiContest: Problema 5 – The Milkman Problem

22Jun11

En el quinto problema nos piden hacer de empresarios y montar una lechería y para ello debemos comprar vacas. El camión que nos traerá las vacas desde Zaragoza tiene un peso máximo (que si no, le revienta los cauchos) así que debemos determinar cuáles vacas comprar de manera que la producción de leche que obtengamos sea la mayor posible.

Siguiendo mi tortura personal planificada, esta solución también la implementé en C++.

Recuerda que en cualquier momento puedes echarle un vistazo al resto de mis soluciones.

Si consideré que el cuarto problema hizo visibles los fallos de la organización, aquí empezaron a salirse un par de gotas más del vaso. Esta vez no solo con respecto a la falta de comunicación en Twitter, que también la hubo porque en ningún momento corrigieron el error (de hecho, al día de hoy, aún está), sino que aquí dos de los tres ejemplos tenían errores en sus datos de entrada. Así sin más.

En su explicación de los datos de entrada nos dicen que nos dan una lista separada por comas de la producción de leche de cada vaca y ¡sorpresa! los últimos dos ejemplos tienen 8 y 10 vacas pero solo nos dan una lista con 7 y 9 producciones de leche. ¿Qué se supone aquí? ¿La última vaca no produce leche? ¿O será quizás la primera? ¿O será la vaca alada de puntos rosas que tenía en la cabeza el que puso los ejemplos sin revisarlos? Al final, resulta que era la última vaca la que no producía (o al menos era la forma de obtener la solución del ejemplo).

Y ¡ojo! No sería la última vez que lo hicieran.

Análisis del problema

En lo que sí nos ayudan (y aquí ahora se les va la mano con lo buena gente) es en hacernos ver que ni meter las vacas más flacas hasta llenar el camión, ni meter las que más produzca hasta llenarlo, no resolverá el problema. Así que nada de avaricia. Debe ser una combinación inteligente.

Intentaré explicar el razonamiento con un ejemplo. Identifiquemos las vacas con un número y coloquémoslas en fila a las puertas del camión. Ahora supongamos que ya hemos metido n-1 vacas y nos toca la vaca n. ¿Cómo sabemos si esa vaca nos conviene? Pues comparamos la producción que tenemos ahora con la que tendríamos si sacamos las vacas necesarias y metemos la n, siempre que quepa.

Eso es más o menos lo que vamos a programar y si la mención de n y n-1 les hace timbrar en el oído la palabra recursión ¡están en lo cierto! Este problema, a diferencia del cuarto, sí admite una solución por recursión, siempre y cuando utilicemos memoización (que si no, no volcaremos la pila pero sí podremos ver el pasto crecer mientras esperamos la solución).

Anteriormente les explicaba que una recursión era una estrategia top-down para resolver un problema y que si queríamos eliminarla, deberíamos darle la vuelta y hacerla bottom-up. Aquí haremos eso. Empezaremos por la primera vaca, en vez de la vaca n y así siempre tendremos los datos necesarios sin necesidad de hacer recursión. La solución recursiva se las puedo ofrecer en pseudo-código si veo insistencia en los comentarios.

Si hasta ahora sospechas que queda un cabo suelto, vas bien. Eso de “quitamos las vacas necesarias” y “siempre que quepa” suena a medio hacer. Para obtener nuestra recursión debemos considerar todos los pesos posibles, desde la vaca más flaca, hasta el peso total del camión.

Por lo tanto, la solución al problema de las vacas es la siguiente:

solucion = max_i(produccion(n,i))
produccion(n,k) =
    max(produccion(n-1,k-peso(n))+leche(n),produccion(n-1,k))

La segunda línea es la recursión de considerar la vaca para alcanzar el peso exacto k. La producción será la máxima entre la que teníamos para el peso k-peso(n) sumada a la leche que nos ofrece la vaca n (lo que se traduce en montar la vaca en el camión) y la producción para el peso k que teníamos sin ella (es decir, mandar a la vaca n a tomar por el saco para el peso k). La primera línea es la producción máxima que podemos alcanzar. Puede que para alcanzarla no tengamos que llenar todo el camión. Por lo tanto, una vez consideradas todas las vacas, buscamos entre todos los posibles pesos de carga, el que nos de una mayor producción.

El análisis está listo. Ahora a echar código.

Solución enviada (incorrecta)

Recuerdas la sensación (si eres estudiante, la debes tener fresca porque esta es la época) que se siente cuando sales de un examen y empiezas a repasar tus respuestas mentalmente y te das cuenta que metiste la pata. Yo tardé 10 minutos, luego de enviada la respuesta, en darme cuenta que mi implementación era incorrecta.

No sé qué gusano loco tenía aconsejándome al oído que me dijo que intentara programar una manera para reducir espacio. – No necesitas una matríz – me decía – con un arreglo y un flag estas hecho. ¡Grave error! Al menos con la recursión que les puse. Con dos arreglos sí que se puede, pero no con uno como lo intenté. Es la edad, estas cosas no me pasaban hace seis años.

Lo que sí debo aplaudir son los ejemplos y pruebas que pusieron. Verán, mi solución solo fallaba en ciertos casos (sobre todo si hay varias vacas con el mismo peso) por lo que no era posible darme cuenta del fallo observando las pruebas. Todas daba OK. Y me parece bien. Fueron unas pruebas justas, que no mostraban los casos bordes y que te daban la responsabilidad como participante de verificar la correctitud del código. +1 para Tuenti por eso.

Si aún quieres ver la solución mala, puedes hacerlo. Pero no hay nada útil que buscar allí. Intenté crearme un conjunto para indicar los pesos en los que ya había admitido a la vaca actual, pues no podía usar la misma vaca dos veces (que es cierto) pero entonces perdía el hecho de que podía usar el mismo peso sin esa vaca.

vector<int> loads(truck+1, 0);

list<int>::iterator it = weight.begin();
list<int>::iterator jt = milk.begin();
for(;it!=weight.end();it++,jt++){
  int currentCowWeight = (*it);
  int currentCowMilk = (*jt);
  set<int> forbidden;
  for(int i=flaca;i<=truck;i++){
    int faltarian = i-currentCowWeight;
    if(faltarian < 0) continue;
    if(forbidden.find(faltarian) == forbidden.end()){
      if(currentCowMilk+loads[faltarian] > loads[i]) {
        loads[i] = currentCowMilk+loads[faltarian];
        forbidden.insert(i);
      }
    }
  }
}

Solución correcta

Ahora lo interesante. Primero la carga de datos (que fue mejor que la anterior pero seguro que se puede mejorar aún más) que la oculto para no pasar tanta vergüenza.

#include <string>
#include <map>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <list>
#include <set>
#include <sstream>
#include <boost/tokenizer.hpp>

using namespace std;

typedef boost::tokenizer<boost::char_separator<char> > tokenizer;

int main() {
  string line;

  while (getline(cin, line)) {
    int cows, truck;
    vector<int> weight;
    vector<int> milk;

    istringstream streamLine(line);
    string weightValues, milkValues;

    streamLine >> cows >> truck >> weightValues >> milkValues;

    boost::char_separator<char> sep(",");
    tokenizer tok(weightValues, sep);
    int flaca = 1<<30;
    for(tokenizer::iterator it = tok.begin(); it != tok.end(); it++){
      int w = atoi((*it).c_str());
      if(w < flaca) {
        flaca = w;
      }
      weight.push_back(w);
    }
    tok.assign(milkValues.begin(), milkValues.end(), sep);
    for(tokenizer::iterator it = tok.begin(); it != tok.end(); it++){
      int m = atoi((*it).c_str());
      milk.push_back(m);
    }

Y luego la solución. Pruebo con las vacas en orden como les mencioné y para cada peso posible que puede cargar el camión veo si puedo usarla. Las líneas 59 y 55 son las dos fórmulas que vimos en el análisis del problema.

    vector<vector <int> > loads(cows, vector<int>(truck+1,0));

    for(int i=0;i<cows;i++){
      for(int j=flaca;j<=truck;j++) {
        int maxAnterior = (i==0) ? 0 : loads[i-1][j];
        int faltarian = j-weight[i];
        if(faltarian < 0) { // la vaca es muy pesada
          loads[i][j] = maxAnterior;
        } else {
          int maxFaltante = (i==0) ? 0 : loads[i-1][faltarian];
          loads[i][j] = max(milk[i]+maxFaltante,maxAnterior);
        }
      }
    }
    int max = *(max_element(loads.back().begin(),loads.back().end()));
    cout << max << endl;
  }
  return 0;
}

Nuevamente, excepto la lectura de datos, me parece que es una implementación bastante limpia. Agradecería a los gurús de C++ que me orienten en cómo hacer una lectura de datos de este estilo de forma elegante.

La otra opción para resolver el problema es con una recursión con memoización, como les comenté antes. O utilizar dos vectores en vez de una matriz entera en mi solución (fíjense que solo necesitamos las columnas i e i-1). No se me ocurre una tercera manera que sea más eficiente.

Espero que los casos del submit de Tuenti puedan sobrevivir a mi solución con bug jejeje.

Y tú ¿cómo lo resolviste?

Anuncios


18 Responses to “Resolviendo el #TuentiContest: Problema 5 – The Milkman Problem”

  1. Hola.

    Supongo que habrás visto mi solución http://pastebin.com/dP7JkL29 explicada en http://www.youtube.com/watch?v=onz6BO1d5bQ, donde un compañero ha matizado que él usó Voraces.

    Supongo que vistas las pruebas finales, los que pensamos en una solución de tipo “buscar la mejor solución de entre todas las posibles”, nos confundimos. Él (@emgallar en YouTube) ha propuesto la solución VORAZ: ordenar por “leche/peso” e ir metiendo.

    ¿Qué te parece a ti?

    • Hola Guillermo ¿Cómo estás? ¿Qué tal te han parecido las soluciones hasta ahora?
      Te pongo un ejemplo usando la información que me das (ordenar por leche/peso y asumo que de mayor a menor e ir metiendo)

      camion = 300
      vacas peso = 100,100,200 50,50,75
      orden = 50/100 50/100 75/100 = 0.5 0.5 0.375
      solucion obtenida = 100 (las dos primeras vacas y la tercera no cabe)
      solucion real = 125 (la primera o segunda vaca y la tercera)

      Si ordenas de menor a mayor es aún peor la cosa. Como ves, la estrategia voraz también falla con esa aproximación.

      Saludos.

      • Hola. Pues gracias, porque por un momento contesté como tú pero luego me entró la duda… miré el código fuente de algunos, y le terminé dando el visto bueno al algoritmo voraz sin dejar de pensar que era mejor Backtracking… pero ahora que me has recordado “el ejemplo” (que no daba con él) ya definitivamente asumo que el voraz no vale. Gracias de nuevo.

        De todas formas, una pregunta… haciéndolo por Dinámica, como tú lo has hecho, ¿has ganado tiempo? En las pruebas del submit me fijé (lo digo en el vídeo) que el tamaño del camión es bastante grande, por lo que la tabla de dinámica se vuelve bastante ancha. ¿Os tardó mucho? En el vídeo ya se ve lo que me tardó a mí… unos 10-20 segundos en un Ubuntu virtualizado.

      • Hola Guillermo.
        No recuerdo el tiempo del submit y los scripts ahora con los problemas “liberados” dan siempre WRONG. No sé qué apretaron los de Tuenti, pero repetir el submit (con el token CHALLENGE_5) me toma 3segs en total.
        La dinámica tiene un orden cuadrático (vacas*camion) mientras que el backtracking es exponencial en función del número de vacas (todas las opciones son 2^vacas). Si pones muchas vacas, el backtracking se dispara. Si son pocas vacas (quizás hasta 20), es admisible.

      • Mmm, fíjate en el vídeo. La batería del submit constaba de camiones de mucha capacidad (40.000 o así) y unas 15 vacas . Si decidí hacer bactracking (con poda) fue porque consideré que -entre la poda y tal- haría menos operaciones… aunque luego se ve que me confundí, ya que en el test había pocas vacas pero en el submit no. Todavía en el quinto problema no me había dado cuenta que el test del submit iba a ser mucho más duro que el otro, y se me disparó.

        Para solucionar eso, se me ocurrió añadir una cosilla: por cada vaca que lea de la entrada, decremento una copia del valor de la capacidad del camión. Si después de leer todas, ese valor es mayor o igual que cero… me entran todas las vacas, por lo que no hago nada más que ponerlas una detrás de otra.

        Creo que eso fue algo que nos faltó hacer y habría estado muy bien. ¿No crees?

      • Sí, definitivamente si son pocas vacas y mucho peso la dinámica se hace más larga. Pero ¿cuánto más pesado pondrían el camión? 40K no es mucho y no afecta tanto al problema como la cantidad de vacas. Piensa la diferencia entre variar el peso de 400 a 40K (100 veces más) y variar la cantidad de vacas entre 15 y 30 (solo el doble).
        Una revisión como la que comentas puede descartar correctamente los casos en que caben todas las vacas. Tienes razón, pudimos agregarla para descartar esos casos y someter al algoritmo solo los casos interesantes.
        De todas formas, no tiene gracia (como problema) que en el camión quepan todas las vacas. La evaluación se haría (seguro) en función del número de vacas (que para eso la ponen “finita”). Te lo digo por experiencia.

  2. Hola.
    Disculpas, pero no tengo a mano el código que hice. De todos modos, explico por encima:
    Para evitar la recursión, empleé una pila (stack de la STL de C++) y una estructura que almacenara los datos para cada estado, al estilo de las técnicas de inteligencia artificial. A ello le puedes aplicar poda y demás métodos para reducir espacio y tiempo.
    Por otro lado, veo que intentas resolver la lectura de datos un poco ” a la Java” 😀 Yo lo resolví usando scanf (sí, de C) Es muy útil y rápido para el formateo de entradas y expresiones regulares. Te dejo un ejemplo de cómo resolví la lectura de direcciones de email de un fichero: http://www.elrincondelc.com/nuevorincon/foros/viewtopic.php?p=59333#59333
    Es cierto que siempre cuesta dominar un lenguaje que no es tu preferido, pero te ha quedado una solución bastante agradable 😉 Espero haberte dado alguna idea para futuros proyectos. Saludos.

    • Hola Christian.
      ¡Es verdad! me había olvidado de scanf por completo ¡qué despiste! lo incluiré en el arsenal. Eso me facilitará un montón la lectura cuando sepa cuántos datos leer. Pero en el caso de las vacas, ¿cómo lees su patrón? Se me ocurre leer el primer entero de la lista y luego los restantes con el formato “,%d” ¿Qué te parece?
      Y sí, definitivamente mi lectura de datos es 100% Java. Ahora que me dedico a la investigación trabajo mucho con Perl donde la lectura de datos es lo máximo pero no tiene un equivalente ni en Java (seguro que no) ni en C++ (creo).
      Gracias por tu consejo y por compartir tu estrategia.

      • La lectura se puede hacer más o menos flexible. Tu idea me gusta 🙂
        He vuelto a escribir algo parecido a lo que hice:

        #include
        #include
        using namespace std;

        int main(){
        int value, truck;
        vector weight, milk;

        while(scanf(“%*d%d”, &truck) == 1){
        while((scanf(“%d”, &value) == 1) && (getchar() == ‘,’))
        weight.push_back(value);
        while((scanf(“%d”, &value) == 1) && (getchar() == ‘,’))
        milk.push_back(value);
        }
        return 0;
        }

        Sencillamente ignoro el número de vacas que me dicen que hay (todo mentira…) y leo cada lista hasta que no queden comas separadoras.

        Y se me había olvidado añadir que, en vistas de ahorrar memoria, cada estado puede estar representado como un bitset, colocando a ‘1’ los bits con la misma posición que la de las vacas que hemos elegido hasta el momento: http://www.cplusplus.com/reference/stl/bitset/
        A las técnicas de backtracking, programación dinámica… insisto en que es muy interesante estimar cotas para cribar resultados parciales peores que la mejor solución obtenida, eliminar nodos repetidos y demás métodos de inteligencia artificial. Incluso sustituir la pila de estados por una cola con prioridades y ramificar los resultados más prometedores: http://www.cplusplus.com/reference/stl/priority_queue/

        Perdón por la extensión. Es un placer compartir código y espero con ganas las siguientes entradas. Aún tengo mucho que aprender 🙂

      • Sabía que algo fallaba 😛
        El código que he publicado antes (al que le falta el contenido colocado entre ) no añade el último elemento de cada vector. Se podría solucionar con un do-while:
        do{ scanf; push; } while(getc == ‘,’);

        Saludos.

  3. 11 Alfredo

    Ese problema es el 0-1 knapsack problem, una variante del problema de la mochila. La mejor implementación usa programación dinámica: http://ace.cs.ohiou.edu/~razvan/courses/cs404/lecture16.pdf

    • Hola Alfredo.
      Tienes toda la razón. Esa es mi implementación. Quizás debí decir explícitamente que la estrategia general se llama Programación Dinámica y mencionar que las vacas y el camión es un disfraz del problema de la mochila con conjuntos finitos de objetos. Quedarían las referencias completas.
      Gracias por la aportación.


  1. 1 Poesía binaria » Recopilación de soluciones para los retos de #tuentiContest . Challenge #5
  2. 2 Resolviendo el #TuentiContest: Problema 6 – The clock « lagunex
  3. 3 Resolviendo el #TuentiContest: Problema 7 – The tile game « lagunex
  4. 4 Resolviendo el #TuentiContest: Problema 10 – Key Combos « lagunex
  5. 5 Resolviendo el #TuentiContest: Problema 11 – Gas stations « lagunex
  6. 6 Resolviendo el #TuentiContest: Problema 15 – The Robot « lagunex

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

w

Conectando a %s


A %d blogueros les gusta esto: