The farm is on the move! Farmer Mike and his n cows have decided that it’s time
ID: 3667071 • 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).
Instead of codes, I want the thorough explanation of how the algorithm is working. Please exlain it as much as possible.
In addition, please include how to prove that the algorithm is correct (correctness of the algorithm) and the runtime analsys.
Explanation / Answer
Algorithm: This problem can be solved by using the Greedy method of algorithm design. General approach of greedy method can be defined as:
-----------------------
Greedy(a,n)
// a[1..n] is the set of n inputs
{
solution:= { }; //initialize the solution
for i := 1 to n do
{
x := Select(a);
if (Feasibile (solution, x) then
solution := Union(solution, x);
}
return solution;
}
From the above general format, we can deduce that a greedy method works in steps, considering one input of the set at each step. Out of n inputs, which input is considered at a particular step is based on some selection criteria termed as greedy criteria (Selection() method). All inputs are arranged in a order based on greedy criteria. Once an input is selected, a decision is made whether the input can be the part of optimal solution (i.e. satisfies objective function). Meaning the selection of input is fieasible or not (Feasible() method). If it is feasible, then it is added to solution (Union() method), otherwise omitted.
For the given problem, following strategy can be adopted:
1. As mentioned above, first we need to define the selection criteria. Meaning how cows will be considered to be loaded onto thetruck so that Mike gets better loading. This can be done by putting the cows in the increasing order of their weights.
For the given example, it will be like this :- (w3,w4,w1,w2,w5) = (1,2,3,3,3)
2. Once the selection criteria is defined, we can select objects in the order as per the selection criteria.
3.Once an object is selected, we need to check the feasibility of our selection. Here it is the available capacity of the truck, which should not be violated by the weight of the selected cow. It means:
Total weights of the cows selected so far < = capacity of truck.
If the selection of a cow violates this constraint, then selecting that cow won't be feasible. It means, for the first trip, cow with weight 1 can be selected. After selecting this cow, remaining capacity of truck is 3, so next cow in the set with weight 2 can also be added for that trip. Once this cow is added, the remaining capacity is 1, hence no other cow is added for that trip.
3. If the constraint is satisfied, then we need to check whether this might satify the objective function or not. In our case, objective function is smallest number of trips. Here, we have selected two cows with weight 1 and 2 (best fitting the capacity of truck) for the trip. This two cows can be moved in the first trip.
Similarly, remaining cows will be considered for next trips depending on the fact whether constraint is satisfied or not.
At the end (once all objects in the set are considered), we will have optimal (smallest) no. of trips required to move the cows.
Formal statement of the algorithm is as follows:
--------------------------------
CowShift(W,w,x,n) {
//W is the capacity of truck, w[1..n] is weight vector in increasing order. x[1..n] is solution vector. n is the no. of cows.
{
for i := 1 to n do x[i] = 0;
trips := 0; //no. of trips
cowsMoved = 0; //no. of cows moved
while cowsMoved <= n do
{
U := W;
for j :=cowsMoved+1 to n do
{
if (w[j] > U) then
{
trips := trips +1;
break;
}
x[j] = 1.0;
U:= U - w[j];
}
cowsMoved := j -1; //no. of cows moved less than 1 cows considered so far.
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.