Problema ACM-ICPC. Stack of Stones. Algoritmos Greedy


Muchas veces en la vida se nos presentan situaciones en las cuáles debemos tomar una decisión, y claro está, siempre tratamos de tomar la decisión que más nos beneficie, salvo algunas excepciones. Pues de esto se trata este artículo, veremos una generalización de algoritmos que utilizan el criterio de “siempre mi mejor opción”, ¿Qué tipos de algoritmos son estos? Pues estamos hablando, de los algoritmos greedy o como son conocidos en español, algoritmos golosos.

Aclarando bien el concepto, diremos que los algoritmos greedy son aquellos en que siempre se trata de tomar la mejor opción de todas las existentes. Aunque debemos conocer que este tipo de algoritmo no siempre conlleva a obtener la mejor solución. Ejemplos clásicos de greedy son los algoritmos: Dijkstra y Kruscal, ambos de la teoría de grafos.

Para un mejor entendimiento de esta clase de algoritmos, analizaremos el problema “Stack of Stones” (pila de piedras), tomado del jurado online coj.uci.cu.

La descripción del problema es la siguiente:

Dados n bultos de piedra, queremos combinarlos todos en un solo bulto. Para realizar esta tarea, podemos seleccionar arbitrariamente dos bultos y fusionarlos en uno, y volver a hacer lo mismo hasta que quede un solo bulto. Combinar dos bultos trae consigo gastar cierta energía, y el costo de esta es la cantidad de piedras del bulto más pequeño, por ejemplo, si combinamos dos bultos con 3 y 5 piedras respectivamente, el costo de la operación es 3 y el bulto obtenido es uno de 8 piedras. Dados la cantidad de bultos, calcule la mínima cantidad de energía que se necesita para hacer el trabajo.

Stack of Stones

Fig1: Stack of Stones

Solución del problema:

Aplicando un algoritmo greedy, nuestra mejor opción es siempre combinar el bulto más pequeño con otro, para gastar la menor cantidad de energía en cada paso, pero si nos fijamos, la mínima cantidad de operaciones para convertir n bultos de piedra en uno sólo son n-1, entonces, ¿con cuál lo fusionamos?, aquí entra nuestro segundo criterio del algoritmo greedy, unir nuestro menor bulto con el mayor, así en cada paso siempre seleccionamos la mínima energía posible y el único bulto que incrementa su tamaño es el mayor.

Representacion de la solución

Fig1: Representacion de la solución

Es decir, la solución sería la suma de los valores de todos los bultos sin incluir el mayor.

Código en C++ que soluciona el problema:

int main()
{
    int t,n,arr[10005];
    cin >> t; //leer la cantidad de casos que habrán en la lectura.
    while(t--)
    {
        cin >> n; //leer la cantidad de bultos de piedra que hay en el caso.
        for(int i = 0; i < n; i++)         {             cin >> arr[i]; //leer la cantidad de piedras por bulto
        }
        sort(arr,arr+n); //ordenamos de menor a mayor
        int sol = 0;
        for(int i = 0; i < n-1; i++)
        {
            sol+=arr[i]; //sumamos todos los valores excepto el último
        }
        cout <<sol<<endl; //mostramos la solución
    }
    return 0;
}

En los problemas greedy siempre están presentes una serie de elementos que debemos tener en cuenta, estos son:

  • Conjunto de candidatos.
  • Función de selección.
  • Función objetivo.

En el caso del problema analizado el conjunto de candidatos son los bultos de piedra, la función de selección sería el hecho de elegir el menor bulto y unirlo con el mayor, y la función objetivo es el coste total de hacer todas las operaciones.

Conclusiones

Los algoritmos greedy son una herramienta poderosa para resolver problemas de optimización, pero no siempre conllevan a encontrar la solución óptima, por lo que muchas veces se requieren fuertes conocimientos de otros algoritmos y técnicas como divide y vencerás o programación dinámica, pero esto son temas de próximos artículos, por ahora esto es todo, no olviden dejar sus comentarios, dudas o sugerencias.