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

Jamborel - Casino Resort in Mombasa, Tanzania - JTM Hub

ReplyDelete› jamborel › 군포 출장샵 jamborel Jamborel Casino Resort Mombasa, Tanzania. Jamborel 아산 출장안마 is a popular destination located on the 경주 출장안마 Chupa River in the Central African 안양 출장샵 Republic. Jamborel 전라남도 출장안마 is a popular destination