Guest User

CH5 Milkman

a guest
Jun 20th, 2011
982
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.io.IOException;
  4. import java.util.StringTokenizer;
  5.  
  6. /*
  7.  * Tuenti Contest
  8.  * Challenge 5 - Milkman
  9.  * Author: Pedro Antonio Pardal Jimena
  10.  * Email: pardal@alu.uma.es
  11.  */
  12.  
  13. public class Milkman
  14. {  
  15.     private static int[] parseNumberList( String s, int n )
  16.     {
  17.         int[] result = new int[n];
  18.        
  19.         StringTokenizer st = new StringTokenizer( s, "," );
  20.        
  21.         for ( int i = 0; i < n; i++ )
  22.         {
  23.             result[i] = Integer.parseInt( st.nextToken() );
  24.         }
  25.        
  26.         return result;
  27.     }
  28.    
  29.     private static int[][] calcularTabla( int n, int w, int[] pesos, int[] litros )
  30.     {
  31.         int[][] tabla = new int[n+1][w+1];
  32.        
  33.         for ( int i = 0; i <= n; i++ )
  34.             tabla[i][0] = 0;
  35.        
  36.         for ( int j = 0; j <= w; j++ )
  37.             tabla[0][j] = 0;
  38.        
  39.         for ( int i = 1; i <= n; i++ )
  40.         {
  41.             for ( int j = 1; j <= w; j++ )
  42.             {
  43.                 if ( pesos[i-1] > j )
  44.                 {  
  45.                     tabla[i][j] = tabla[i-1][j];
  46.                 }
  47.                 else
  48.                 {  
  49.                     if ( tabla[i-1][j] > litros[i-1] + tabla[i-1][j - pesos[i-1]] )
  50.                         tabla[i][j] = tabla[i-1][j];
  51.                     else
  52.                         tabla[i][j] = tabla[i-1][j - pesos[i-1]] + litros[i-1];
  53.                 }
  54.             }
  55.         }
  56.        
  57.         return tabla;
  58.     }
  59.    
  60.     private static int parseInput( String linea )
  61.     {
  62.         StringTokenizer st = new StringTokenizer( linea, " " );
  63.        
  64.         int n = Integer.parseInt( st.nextToken() );
  65.         int w = Integer.parseInt( st.nextToken() );
  66.        
  67.         int[] pesos = parseNumberList( st.nextToken(), n );
  68.         int[] litros = parseNumberList( st.nextToken(), n );
  69.        
  70.         int[][] tabla = calcularTabla( n, w, pesos, litros );
  71.        
  72.         return tabla[n][w];
  73.     }
  74.    
  75.     public static void main( String[] args ) throws IOException
  76.     {
  77.         BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
  78.        
  79.         while ( reader.ready() )
  80.         {
  81.             String linea = reader.readLine();
  82.             int result = parseInput( linea );
  83.            
  84.             System.out.println( result );
  85.         }
  86.     }
  87. }
RAW Paste Data