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[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;
	}

}

No comments:

Post a Comment