Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 18
The greedy algorithm for the thirsty baby problem begins by
sorting the liquids into nonincreasing order of
si. Then the liquids are considered
in this order. When liquid i is considered,
we select as much of it as possible without exceeding the total
capacity constraint t. That is, we set
xi to the largest number
<= ai so that the current sum of the
xjs does not exceed
t. If this sum becomes
t, we terminate. Otherwise, we move on to the
next liquid in sorted order.
The above greedy method guarantees optimal solutions. The proof
is similar to that of Exercise 17.
Consider any instance of the thirsty baby problem.
We may assume that the liquids are given in nonincreasing order of
si.
Let x1 ... xn
be the greedy solution and let
y1 ... yn be an optimal solution.
We shall show that both solutions earn the same satisfaction and so the greedy
solution is also optimal.
Let j be the least integer such that
xi = yi,
1 <= i < j and xj != yj.
If no such j exists, the two soultions are the same and
so the greedy solution is optimal. Assume such a j exists.
From the way the greedy algorithm works and the fact
that the optimal solution is a feasible solution, we conclude that
xj > yj.
If we increase the amount of liquid j in the
optimal solution to xj
and reduce the amount of liquids j+1, j+2, ...
to compensate for the increased capacity used by liquid j,
the satisfaction cannot decrease because we are replacing lower satisfaction
liquids by higher or equal satisfaction ones. This transformation,
therefore, yields a new optimal solution for which
the least integer j such that
xi = yi,
1 <= i < j and xj != yj
(if it exists) is larger than for the old optimal solution.
By applying this transformation a finite number of times,
we convert the original
optimal solution into the greedy solution without decreasing
the satisfaction earned. So the greedy solution must also be optimal.