Challenge 5: The Milkiman Problem

_________________________________________________________________________
You are an entrepreneur in Madrid, and have a brilliant idea to open a milk shop in Plaza Mayor. As you are very conscious, you want the milk you sell to be perfectly natural and fresh, and for that reason, you are shipping healthy cows from Zaragoza region to Madrid. At your disposal you have a truck with the weight limit, and a group of cows available for sale. Each cow can weigh differently, and produce a different amount of milk per day.

Your goal as an entrepreneur is to choose which cows to buy and transfer in your truck, so you can maximize the milk production, observing the truck weight limit.

Input Total number cows in Zaragoza area that are for sale.

Input Total weight you truck can handle.

Input List of cow weights, one per cow.

Input List of cow milk production in liters per day, one per cow.

Output the maximum amount of milk production you can get.

Example

Cow # Cow Weight in Kilograms Cow Milk Production per Day  1 360 40  2 250 35  3 400 43  4 180 28  5 50 12  6 90 13 700 kg

Cow #	Cow Weight in Kilograms	Cow Milk Production per Day
1	360	40
4	180	28
5	50	12
6	90	13
4x	total 700kg	total 93L milk production

Input and output format

Input and output come from standard input and output streams.
Input 4 parameters:

• Number of cows available for sale, e.g. 6
• Truck weight limit in kilograms, e.g. 700
• Comma-separated list of cow weights, e.g. 360,250,400,180,50,90
• Comma-separated list of cow milk production, e.g. 40,35,43,28,12,13

Output 93

Sample input

6 700 360,250,400,180,50,90 40,35,43,28,12,13 8 1000 223,243,100,200,200,155,300,150 30,34,28,45,31,50,29 10 2000 340,355,223,243,130,240,260,155,302,130 45,50,34,39,29,40,30,52,31

Sample output

93 188 320

TEST

8 6299 281,440,33,89,451,155,532,545 69,67,65,73,69,14,35,41
8 7453 174,150,413,414,604,121,54,79 89,35,107,99,104,100,63,109
12 5571 325,300,76,134,80,159,60,342,364,133,52,118 45,61,25,56,62,11,23,41,32,62,51,42
18 5143 135,125,46,165,128,185,14,106,110,132,147,140,97,255,166,185,271,204 10,16,10,3,5,11,18,2,8,16,4,3,3,13,7,0,5,11
13 4561 165,209,319,277,35,212,211,283,45,342,179,199,94 25,9,18,20,25,1,14,27,8,28,15,4,0
19 5565 112,86,218,62,62,186,249,84,247,129,232,248,262,15,154,145,170,217,211 32,8,15,27,28,10,33,25,30,8,2,10,26,11,15,16,23,6,32

_________________________________________________________________________
UserInterface Class:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * Clase encargada de mantener el bucle de ejecución del programa hasta el fin de linea.
 * @author Javier de Pedro López
 */
public class UserInterface {

    /**
     * Permite mantener el bucle de lecutra.
     */
    public void run() throws IOException{
        String line;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        //Bucle que realiza las lecturas hasta que lo recibido sea EOF (null)
        do{
            line = reader.readLine();
            if  (line != null && !line.trim().equals("")){
                StringTokenizer tokens = new StringTokenizer(line," ");
                //Creamos el solucionador del problema
                Milkiman milkiman = new Milkiman(tokens.nextToken(),tokens.nextToken(),tokens.nextToken(),tokens.nextToken());
                System.out.println(milkiman.getMilkSolution());
            }
        } while(line != null);
    }
}

Milkiman Class:

import java.util.StringTokenizer;

/**
 * Soluciona el problema del lechero de igual forma que se soluciona el problema de la mochila.
 * @author Javier de Pedro López
 */
public class Milkiman {

    //ATRIBUTOS//
    private int _truck;
    private int _numCows;
    private int[] _weight;
    private int[] _milk;
    private int _bestMilkSolution;

    //CONSTRUCTOR//
    /**
     * Intancia un Milkiman para la obtencion de la mejor solucion al problema.
     * @param numCows numero de vacas.
     * @param truck peso del camion.
     * @param cows pesos de las vacas separados por comas.
     * @param milk litros de leche separados por comas.
     */
    public Milkiman(String numCows, String truck, String cows, String milk){
        _numCows = Integer.valueOf(numCows);
        _truck = Integer.valueOf(truck);
        int B[][];

        _milk = new int [_numCows+1];
        _weight = new int [_numCows+1];

        //Introducimos los valores en los arrays
        StringTokenizer tokenCow = new StringTokenizer(cows,",");
        StringTokenizer tokenMilk = new StringTokenizer(milk,",");
        for (int k = 1; k             _weight [k] = Integer.valueOf(tokenCow.nextToken());
            if (tokenMilk.hasMoreElements()){
                _milk [k] = Integer.valueOf(tokenMilk.nextToken());
            }else{
                _milk [k] = 0;
            }
        }

        // Inicializamos B
        B = new int [_numCows+1][_truck+1];
        for (int w = 0; w             B[0][w] = 0;
        }

        // Calculamos el valor que consideramos el mejor
        for (int k = 1; k = _weight[k]; w--){
                if (_milk[k] + B[k-1][w - _weight[k]] > B[k-1][w]){
                    B[k][w] = _milk[k] + B[k-1][w-_weight[k]];
                }else{
                    B[k][w] = B[k-1][w];
                }
            }
            System.arraycopy(B[k - 1], 0, B[k], 0, _weight[k]);
        }

        // Asociamos el resultado con lo que nos ha salido.
        _bestMilkSolution = B[_numCows][_truck];

    }

    //METODOS//
    /**
     * Permite obtener la mejor solucion calculada por el algoritmo.
     * @return la mejor solucion.
     */
    public int getMilkSolution(){
        return _bestMilkSolution;
    }
}