The Milkman Java Tuenti Contest

/****************************************
 ** Fichero Vaca.java
 ***************************************/

package theMilkman;

public class Vaca implements Comparable {

    private int peso;
    private int lecheDia;

    public Vaca(int peso, int lecheDia) {
        this.peso = peso;
        this.lecheDia = lecheDia;
    }

    public Vaca() {
        this(0, 0);
    }

    public int getPeso() {
        return peso;
    }

    public void setPeso(int value) {
        peso = value;
    }

    public int getLecheDia() {
        return lecheDia;
    }

    public void setLecheDia(int value) {
        lecheDia = value;
    }

    public double getRatio() {
        return lecheDia / peso;
    }

    @Override
    public int compareTo(Object o) {
        Vaca vaca = (Vaca) o;
        if (peso > vaca.peso) {
            return -1;
        } else if (peso == vaca.peso) {
            if (lecheDia > vaca.lecheDia) {
                return -1;
            }
        }
        return 1;
    }

    @Override
    public String toString() {
        return "Peso: " + peso + " Litros Día: " + lecheDia;
    }

}

/****************************************
 ** Fichero Main.java
 ***************************************/


package theMilkman;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static List lista = new ArrayList();
    public static int numeroVacas;
    public static int pesoCamion;
    public static int mejorSolucion;

    public static void backtracking(int pesoActual, int lecheActual,
            int elementoActual) {
        boolean solucionMayor = false;
        for (int i = elementoActual + 1; i < numeroVacas + 1; i++) {
            int pesoAux = pesoActual + ((Vaca) lista.get(i)).getPeso();
            if (pesoAux < pesoCamion) {
                backtracking(pesoActual + ((Vaca) lista.get(i)).getPeso(),
                        lecheActual + ((Vaca) lista.get(i)).getLecheDia(), i);
                solucionMayor = true;
            }
        }
        if (!solucionMayor && lecheActual > mejorSolucion) {
            mejorSolucion = lecheActual;
        }
    }

    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        try {
            while (br.ready()) {
                String line = br.readLine();
                StringTokenizer tokens = new StringTokenizer(line);
                numeroVacas = Integer.parseInt(tokens.nextToken());
                pesoCamion = Integer.parseInt(tokens.nextToken());
                String pesosVacas = tokens.nextToken();
                StringTokenizer tokensPesos = new StringTokenizer(pesosVacas,
                        ",");
                String litrosVacas = tokens.nextToken();
                StringTokenizer tokensLitros = new StringTokenizer(litrosVacas,
                        ",");
                if (tokensLitros.countTokens() < numeroVacas)
                    numeroVacas = tokensLitros.countTokens();
                while (tokensLitros.hasMoreTokens()
                        && tokensPesos.hasMoreTokens()) {
                    Vaca vaca = new Vaca(Integer.parseInt(tokensPesos
                            .nextToken()), Integer.parseInt(tokensLitros
                            .nextToken()));
                    lista.add(vaca);
                }
                Collections.sort(lista);
                lista.add(0, new Vaca()); //nodo para hacer de cabecera
                mejorSolucion = 0;
                backtracking(0, 0, 0);
                System.out.println(mejorSolucion);
                lista.clear();
            }
        } catch (Exception e) {
        }

    }

}