javipinero

The Milkman Java Tuenti Contest

Jun 21st, 2011
963
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /****************************************
  2.  ** Fichero Vaca.java
  3.  ***************************************/
  4.  
  5. package theMilkman;
  6.  
  7. public class Vaca implements Comparable {
  8.  
  9.     private int peso;
  10.     private int lecheDia;
  11.  
  12.     public Vaca(int peso, int lecheDia) {
  13.         this.peso = peso;
  14.         this.lecheDia = lecheDia;
  15.     }
  16.  
  17.     public Vaca() {
  18.         this(0, 0);
  19.     }
  20.  
  21.     public int getPeso() {
  22.         return peso;
  23.     }
  24.  
  25.     public void setPeso(int value) {
  26.         peso = value;
  27.     }
  28.  
  29.     public int getLecheDia() {
  30.         return lecheDia;
  31.     }
  32.  
  33.     public void setLecheDia(int value) {
  34.         lecheDia = value;
  35.     }
  36.  
  37.     public double getRatio() {
  38.         return lecheDia / peso;
  39.     }
  40.  
  41.     @Override
  42.     public int compareTo(Object o) {
  43.         Vaca vaca = (Vaca) o;
  44.         if (peso > vaca.peso) {
  45.             return -1;
  46.         } else if (peso == vaca.peso) {
  47.             if (lecheDia > vaca.lecheDia) {
  48.                 return -1;
  49.             }
  50.         }
  51.         return 1;
  52.     }
  53.  
  54.     @Override
  55.     public String toString() {
  56.         return "Peso: " + peso + " Litros Día: " + lecheDia;
  57.     }
  58.  
  59. }
  60.  
  61. /****************************************
  62.  ** Fichero Main.java
  63.  ***************************************/
  64.  
  65.  
  66. package theMilkman;
  67.  
  68. import java.io.BufferedReader;
  69. import java.io.InputStreamReader;
  70. import java.util.ArrayList;
  71. import java.util.Collections;
  72. import java.util.List;
  73. import java.util.StringTokenizer;
  74.  
  75. public class Main {
  76.  
  77.     public static List lista = new ArrayList();
  78.     public static int numeroVacas;
  79.     public static int pesoCamion;
  80.     public static int mejorSolucion;
  81.  
  82.     public static void backtracking(int pesoActual, int lecheActual,
  83.             int elementoActual) {
  84.         boolean solucionMayor = false;
  85.         for (int i = elementoActual + 1; i < numeroVacas + 1; i++) {
  86.             int pesoAux = pesoActual + ((Vaca) lista.get(i)).getPeso();
  87.             if (pesoAux < pesoCamion) {
  88.                 backtracking(pesoActual + ((Vaca) lista.get(i)).getPeso(),
  89.                         lecheActual + ((Vaca) lista.get(i)).getLecheDia(), i);
  90.                 solucionMayor = true;
  91.             }
  92.         }
  93.         if (!solucionMayor && lecheActual > mejorSolucion) {
  94.             mejorSolucion = lecheActual;
  95.         }
  96.     }
  97.  
  98.     public static void main(String[] args) {
  99.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  100.  
  101.         try {
  102.             while (br.ready()) {
  103.                 String line = br.readLine();
  104.                 StringTokenizer tokens = new StringTokenizer(line);
  105.                 numeroVacas = Integer.parseInt(tokens.nextToken());
  106.                 pesoCamion = Integer.parseInt(tokens.nextToken());
  107.                 String pesosVacas = tokens.nextToken();
  108.                 StringTokenizer tokensPesos = new StringTokenizer(pesosVacas,
  109.                         ",");
  110.                 String litrosVacas = tokens.nextToken();
  111.                 StringTokenizer tokensLitros = new StringTokenizer(litrosVacas,
  112.                         ",");
  113.                 if (tokensLitros.countTokens() < numeroVacas)
  114.                     numeroVacas = tokensLitros.countTokens();
  115.                 while (tokensLitros.hasMoreTokens()
  116.                         && tokensPesos.hasMoreTokens()) {
  117.                     Vaca vaca = new Vaca(Integer.parseInt(tokensPesos
  118.                             .nextToken()), Integer.parseInt(tokensLitros
  119.                             .nextToken()));
  120.                     lista.add(vaca);
  121.                 }
  122.                 Collections.sort(lista);
  123.                 lista.add(0, new Vaca()); //nodo para hacer de cabecera
  124.                 mejorSolucion = 0;
  125.                 backtracking(0, 0, 0);
  126.                 System.out.println(mejorSolucion);
  127.                 lista.clear();
  128.             }
  129.         } catch (Exception e) {
  130.         }
  131.  
  132.     }
  133.  
  134. }
RAW Paste Data