Apple Delivery

Here is a problem that I came across recently (from here):

The distance between the towns A and B is 1000 miles. There are 3000 apples in A, and the apples have to be delivered to B. The available car can take 1000 apples at most. The car driver has developed an addiction to apples: when he has apples aboard he eats 1 apple with each mile made. Figure out the strategy that yields the largest amount of apples to be delivered to B.

Now, there are two or three interesting ways to solve this problem.

The sure shot way is to use dynamic programming. We define the value function as

U(n,d) = the maximum number of apples that can be delivered to a distance d starting from an initial amount of n apples (under the conditions of the problem)

V(n,d) = the maximum of apples that can be delivered to a distance d starting from an initial amount of n apples if there are no intermediate stops

First, we derive an expression for V(n,d). Let c be the capacity of the car (in our case 1000). We have:

V(n,d) = 0, if d > c (you cannot go farther than c in single run)
= Max(n - d , 0), if n < c
= Floor(n/c) (c - d) + Max ( n mod c - d, 0)

Now the Bellman equation for U(n,d) can be written as:

U(n,d) = max_{1<= u <= d} U( V (n, u), d - u)

With the termination condition

U(n,0) = n (there is no transportation needed, thus no apple loss)

We can now program this DP and solve the problem to get the solution:

U(3000, 1000) = 833

But, is there a simpler way?

I could think of two arguments.

First we can use a greedy approach. Talking in monetary terms, our initial wealth is 1000 apples and the cost of transporting the apple is 1 apple/mile.

Consider the initial simplistic guess of transporting 3000 apples in 3 batches in one go. In each batch the number of apples transported is 1000, the average cost per apple is 1 apple per apple moved thus the total cost is 1000 x 1 = 1000. Thus we end up with 0 apples on the other end.

But is there a way we can decrease the average cost of transporting the apples so that at the end we have a positive balance?

The answer turns out to be yes. Consider moving 1000 apples by just one mile. The cost is 1 apple and the average cost per apple is 1/1000 much smaller than the 1 per apple cost we had earlier. (Of course, this is the cost for just one mile whereas earlier we had moved the apples a 1000 miles). But this gives the idea that if we follow a greedy approach and move the apples one mile at a time, the average cost per apple will be the lowest possible.

In fact, this approach works and we can easily write out a recursion for computing the number of apples left.

Let N(d) = the number of apples we have in the dth mile.

We have:

N(0) = 3000
N(d) = N(d-1) - Ceiling(N(d-1)/c)

Solving this recurrence forward gives us the answer N(1000) = 833.
In fact, if we recheck the solution to our DP, it will indeed show that the optimal solution has the corresponding N(d) values given by the above recurrence.

Now when we see a recurrence, usually there is a differential equation lurking around. It turns out to be the case here also.

Note that for small c (compared to N(d)), the above recurrence can be approximated as

N(0) = 3000
N(d) = N(d-1) - N(d-1)/c

Passing into infinitesimals, we have

N(0) = 3000
dN(x)/dx = - N(x)/c

We immediately get the solution as

N(x) = N(0) Exp(-x/c)

In our case, we get N(1000) = 1103.64.

Of course, we are off by about 32.5%, but note that N(0)/c = 3, which is not really large, so our approximation is also not that valid.

But if we had N(0) = 30000, say, we would get N(1000) = 11036.4 whereas the accurate solution from the difference equation (or the DP) is 10720, giving us an error of only about 3% - which is not bad compared to the effort involved in solving the DP.

Tailpiece:

We can also invert the problem and compute the farthest distance that you can go with the initial number of apples. For our original problem with 3000 apples, the answer turns out to be 1833 miles (again following the mile-by-mile strategy).

There is also a related problem where instead of the apples the car is transporting fuel and it consumes 1 gallon per mile traveled both ways. The goal is to find out the maximum gallons of fuel that can be transported to 1000 miles.

You can work out the DP for this :-)