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[0]);
		int tWeight = Integer.parseInt(args[1]);
		String[] wei = args[2].split(",");
		String[] prod = args[3].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;
	}

}