Paréntesis Balanceados - Problema UVA 673

Este problema busca identificar si una cadena conformada exclusivamente por paréntesis redondos y cuadrados está correctamente formada. La descripción del problema se encuentra en el sitio de UVA en la dirección: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=614

Para resolver el problema se recurre a una pila como estructura de datos en la que se guardan los paréntesis izquierdos que se van leyendo, y que deben ser extraídos correctamente cuando aparezcan los paréntesis derechos en la expresión a evaluar.

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        // En la primera línea de la entrada se lee el número de casos a evaluar
        int numeroCasos = Integer.parseInt(in.readLine());

        // Cada caso se evalúa en forma individual
        for(int i=0; i<numeroCasos; i++) {
            boolean respuesta = evaluarCadena(in.readLine().toCharArray());
            if(respuesta==true) System.out.println("Yes");
            if(respuesta==false) System.out.println("No");
        }
    }

    boolean evaluarCadena(char[] cadena) {
        // Una pila es la estructura ideal para la evaluación de cadenas balanceadas
        Stack<Character> cola = new Stack<Character>();
        for(char c: cadena) {
            // los paréntesis izquierdos se agregan a la pila, mientras que los derechos
            // requieren sacar el elemento opuesto de la pila, de lo contrario hay error.
            if(c=='[' || c=='(') { cola.push(c); continue; }
            if(cola.isEmpty()) return false;
            if(c==')' && cola.pop()!='(') return false;
            if(c==']' && cola.pop()!='[') return false;
        }
        if(!cola.isEmpty()) return false;
        else return true;
    }
}

Problema de la mochila - Algoritmos Voraces

Si bien la solución por backtracking permite obtener la mejor solución al problema de la mochila, existe el problema de que cuando la cantidad de elementos a evaluar es relativamente grande, los tiempos de respuesta se vuelven prohibitivos. Por otro lado, la solución de agregar primero los elementos más costosos, o lo más livianos, no garantiza una solución óptima, o por lo menos parecida a la óptima.

Estas dos aproximaciones representan el concepto de algoritmos voraces, donde se selecciona una estrategia que permite decidir si un elemento se agrega o no a la solución. En los casos mencionados se utilizaba la estrategia del mayor costo o la del menor peso. Una mejor solución se presenta cuando se utiliza el costo por unidad de peso para ordenar los elementos, de esta manera, un elemento muy caro no se agrega si pesa demasiado en comparación con otro de menor valor, pero de mucho menor peso. La función resolverProblema queda entonces de la siguiente manera:

    public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor/x.peso - y.valor/y.peso);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

En cuanto al desempeño de este método, su complejidad es la equivalente al proceso de ordenación de la lista de elementos por su valor por unidad de peso, que es O(N log N), ya que el proceso de llenado de la mochila es lineal.

En el caso de ejemplo, este método da una respuesta con un peso total de 18 Kg y un costo de $945, mientras que la respuesta obtenida por backtracking es de 20 Kg con un costo de $955, lo que muestras que se obtiene un valor muy cercano al óptimo en una fracción del tiempo.