## Thursday, August 25, 2011

### The Milkman Problem

Tuenti recently made the Tuenti Programming Contest 2011 where they  proposed some programming problems.

One of these problems is The Milkman Problem where there is a group of cows for sale, each with different milk production and weight, and we also have a truck with a weight limit.
We have to decide what cows we buy and transfer in our track maximizing the amount of milk production per day.

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,28
10 2000 340,355,223,243,130,240,260,155,302,130 45,50,34,39,29,40,30,52,31,29
```
Sample output
```93
188
320
```

I made a recursive algorithm that does an iteration per cow. In each iteration it checks whether taking or not the cow we get a optimal solution and returns the higher one.

The complexity of the algorithm in the big O notation is O(N^2) being N the number of cows.

```public final class Main {

public static void main(String args[]) {

// we parse the input
int tCows = Integer.parseInt(args);
int tWeight = Integer.parseInt(args);
String[] wei = args.split(",");
String[] prod = args.split(",");

// we print the solution given the the MaxProduction method
System.out.println(MaxProduction(tCows, tWeight, wei, prod, 0, 0, 0));
}

private static int MaxProduction(int tCows, int tWei, String[] wei,
String[] prod, int iter, int aProd, int aWei) {

// we check if there are cows left to process
if (iter < tCows) {

// we make sure not to exceed the weight restrictions imposed
if (aWei + Integer.parseInt(wei[iter]) <= tWei) {

// we return the higher production between taking or not the current cow
return Math.max(Math.max(
MaxProduction(tCows, tWei, wei, prod, iter + 1, aProd
+ Integer.parseInt(prod[iter]),
aWei + Integer.parseInt(wei[iter])), aProd),
Math.max(
MaxProduction(tCows, tWei, wei, prod, iter + 1,
aProd, aWei), aProd));
} else {
// we do not take the current cow as it does not fit
return MaxProduction(tCows, tWei, wei, prod, iter + 1, aProd,
aWei);
}
}
return aProd;
}

}
```