The farm is on the move! Farmer Mike and his n cows have decided that it’s time
ID: 3666220 • Letter: T
Question
The farm is on the move! Farmer Mike and his n cows have decided that it’s time they leave Santa
Cruz and head for their new home in Saskatchewan. However, there are two issues. First off, Farmer
Mike only has one truck, and so he’s going to need to make a number of trips in order to get all of
his cows to their new digs. Second, the cows have a strict pecking order C1, C2,...,Cn and insist on
traveling to the new farm in that order. The truck can hold up to W pounds without bottoming out and
each cow has an individual weight wi.
For example, if W = 4 and (w1, w2, w3, w4, w5) = (3, 3, 1, 2, 3), the first truckload can only contain
the first cow. This is because: (i) C2 can not fit (since 3+3 > 4), while (ii) adding some other cow
that fits, e.g., C3, would result to the cows traveling out of order, which is unacceptable. The second
truckload, clearly, can fit both C2, C3. The question is: “should it”? Or does it some times make sense
to not put on the truck a cow that fits, in this case C3, in order to get a better loading down the road?
Get Farmer Mike out of this bind by giving him an algorithm that always moves the cows in the small-
est possible number of trips (subject to the total weight and ordering conditions mentioned above).
Explanation / Answer
package com.he.capillary;
public class CowWeightProblem {
public static void main(String[] args) {
getSmallest(4l, new long[] { 1, 3, 3, 1, 2, 3, 4 });
}
public static void getSmallest(long totalWeight, long[] weights) {
int i = 0;
int sum = 0;
long tripCount = 0;
boolean isValid = true;
while (i < weights.length) {
if (weights[i] > totalWeight) {
isValid = false;
System.out.println("Invalid Data..");
break;
}
sum += weights[i];
if (sum > totalWeight) {
sum -= weights[i];
tripCount++;
i--;
sum = 0;
} else if (sum == totalWeight) {
tripCount++;
sum = 0;
}
i++;
}
if (isValid && sum != 0 && sum <= totalWeight) {
tripCount++;
}
System.out.println(tripCount);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.