Page 221 - Discrete Mathematics and Its Applications
P. 221

200  3 / Algorithms


                                                Proof: We will use a proof by contradiction. Suppose that there is a positive integer n such that
                                                there is a way to make change for n cents using quarters, dimes, nickels, and pennies that uses

                                                fewer coins than the greedy algorithm finds. We first note that q , the number of quarters used
                                                in this optimal way to make change for n cents, must be the same as q, the number of quarters
                                                used by the greedy algorithm. To show this, first note that the greedy algorithm uses the most


                                                quarters possible, so q ≤ q. However, it is also the case that q cannot be less than q. If it were,
                                                we would need to make up at least 25 cents from dimes, nickels, and pennies in this optimal
                                                way to make change. But this is impossible by Lemma 1.
                                                    Because there must be the same number of quarters in the two ways to make change, the
                                                value of the dimes, nickels, and pennies in these two ways must be the same, and these coins
                                                are worth no more than 24 cents. There must be the same number of dimes, because the greedy
                                                algorithm used the most dimes possible and by Lemma 1, when change is made using the fewest
                                                coins possible, at most one nickel and at most four pennies are used, so that the most dimes
                                                possible are also used in the optimal way to make change. Similarly, we have the same number
                                                of nickels and, finally, the same number of pennies.

                                                    A greedy algorithm makes the best choice at each step according to a specified criterion.
                                                The next example shows that it can be difficult to determine which of many possible criteria to
                                                choose.

                                 EXAMPLE 7      Suppose we have a group of proposed talks with preset start and end times. Devise a greedy
                                                algorithm to schedule as many of these talks as possible in a lecture hall, under the assumptions
                                                that once a talk starts, it continues until it ends, no two talks can proceed at the same time, and
                                                a talk can begin at the same time another one ends. Assume that talk j begins at time s j (where
                                                s stands for start) and ends at time e j (where e stands for end).

                                                Solution: To use a greedy algorithm to schedule the most talks, that is, an optimal schedule, we
                                                need to decide how to choose which talk to add at each step. There are many criteria we could
                                                use to select a talk at each step, where we chose from the talks that do not overlap talks already
                                                selected. For example, we could add talks in order of earliest start time, we could add talks in
                                                order of shortest time, we could add talks in order of earliest finish time, or we could use some
                                                other criterion.
                                                    We now consider these possible criteria. Suppose we add the talk that starts earliest among
                                                the talks compatible with those already selected. We can construct a counterexample to see that
                                                the resulting algorithm does not always produce an optimal schedule. For instance, suppose that
                                                we have three talks: Talk 1 starts at 8 a.m. and ends at 12 noon, Talk 2 starts at 9 a.m. and ends
                                                at 10 a.m., and Talk 3 starts at 11 a.m. and ends at 12 noon. We first select the Talk 1 because it
                                                starts earliest. But once we have selected Talk 1 we cannot select either Talk 2 or Talk 3 because
                                                both overlap Talk 1. Hence, this greedy algorithm selects only one talk. This is not optimal
                                                because we could schedule Talk 2 and Talk 3, which do not overlap.
                                                    Now suppose we add the talk that is shortest among the talks that do not overlap any of those
                                                already selected. Again we can construct a counterexample to show that this greedy algorithm
                                                does not always produce an optimal schedule. So, suppose that we have three talks: Talk 1 starts
                                                at 8 a.m. and ends at 9:15 a.m., Talk 2 starts at 9 a.m. and ends at 10 a.m., and Talk 3 starts at
                                                9:45 a.m. and ends at 11 a.m. We select Talk 2 because it is shortest, requiring one hour. Once
                                                we select Talk 2, we cannot select either Talk 1 or Talk 3 because neither is compatible with
                                                Talk 2. Hence, this greedy algorithm selects only one talk. However, it is possible to select two
                                                talks, Talk 1 and Talk 3, which are compatible.
                                                    However, it can be shown that we schedule the most talks possible if in each step we select
                                                the talk with the earliest ending time among the talks compatible with those already selected.
                                                We will prove this in Chapter 5 using the method of mathematical induction. The first step we
                                                will make is to sort the talks according to increasing finish time. After this sorting, we relabel
                                                the talks so that e 1 ≤ e 2 ≤ ... ≤ e n . The resulting greedy algorithm is given as Algorithm 7. ▲
   216   217   218   219   220   221   222   223   224   225   226