The farm is on the move! Farmer Mike and his n cows have decided that its 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 hes 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.