Ch16: Greedy Algorithms

tags: algorithm

• contributed by < TYChan6028 >
• textbook: Introduction to Algorithms, Third Edition

16-1 Coin changing

Consider the problem of making change for

$n$ cents using the fewest number of coins. Assume that each coin’s value is an integer.

a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.

Algorithm

1. Pick the coin with the largest denomination of
   $d_k\le n$ cents and add it to the change.
2. Update
   $n$ to the remaining owed amount.
3. Repeat 1. and 2. until the full amount is payed.

Proof

In order to prove our solution optimal, we have to show that our solution satisfies the greedy-choice property and exhibits optimal substructure.

• Let the owed change be
  $n$ cents.
• Let
  $D=\{1,5,10,25\}$ represent all existing denominations sorted in monotonically-increasing order.

1. Greedy-choice property

The first key ingredient is the greedy-choice property: we can assemble a globally optimal solution by making locally optimal (greedy) choices. – textbook, p.424

Consider the optimal way to change

$d_k\le n<d_{k+1}$ (

$d_5=\mathrm{\infty }$): The greedy choice takes coin

$c_k$.

• Claim: Any optimal solution
  $Opt$ must also take coin
  $c_k$.

Say

$Opt$ does not include

$c_k$, then

$Opt$ must only consist of coins

$c_1...c_{k-1}$. This means that coins

$c_1...c_{k-1}$ must add up to

$n$.

k	$d_k$	Constraints	Max. value of $c_1...c_{k-1}$ in any $Opt$
1	1	$P\le 4$
2	5	$N\le 1$	$1\times 4=4$
3	10	$N+D\le 2$	$4+5\times 1=9$
4	25	$unlimited$	$4+10\times 2=24$

As we can see from the chart,

$\sum _{i=1}^{k-1}count(c_i)d_i<d_k\le n$, which shows that no optimal solution exists under this assumption.

Therefore, coin

$c_k$ is indeed the greedy choice to make. This reduces the problem to coin-changing

$n-d_k$ cents, which can again be optimally solved using the greedy-choice property.

2. Optimal substructure

A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. – textbook, p.425

Let

$M[i]$ be the minimum number of coins needed to coin-change

$i$ cents.
Suppose

$Opt$ is an optimal solution to

$M[i]$, then:

• $Opt-\{c_1\}$ is an optimal solution to
  $M[i-d_1]$
• $Opt-\{c_2\}$ is an optimal solution to
  $M[i-d_2]$
• $Opt-\{c_3\}$ is an optimal solution to
  $M[i-d_3]$
• $Opt-\{c_4\}$ is an optimal solution to
  $M[i-d_4]$

⟹

$M[i]=mi{n}_{1\le j\le 4}(M[i-d_j])+1$

Therefore, by substituting

$M[i=n]$, the

$\{1,5,10,25\}$ cashier's algorithm exhibits optimal substructure.

b. Suppose that the available coins are in the denominations that are powers of

$c$, i.e., the denominations are

$c^0,c^1,...,c^k$ for some integers

$c>1$ and

$k\ge 1$. Show that the greedy algorithm always yields an optimal solution.

1. Greedy-choice property

• Conjecture: Making the greedy choice at every iteration leads to a globally optimal solution.

Let

$j$ be such that

$c^j\le n<c^{j+1}(j>k\to j=k)$ and the greedy algorithm returns

$A=\{c_j\}+A^{\prime }$ where

$A$ is a solution. Let

$Opt$ be an optimal solution for

$n$.

1. Basis step
   If

   $A^{\prime }=\mathrm{\varnothing }$, then
   $n=c^j$ and
   $A=\{c_j\}=Opt$.

2. Inductive step
   Assume

   $A^{\prime }=Op{t}^{\prime }\ne \mathrm{\varnothing }$ for
   $n-c^j$, then
   $A=\{c_j\}+A^{\prime }=\{c_j\}+Op{t}^{\prime }=Opt$.
   According to our conjecture,
   $Opt$ must also contain a
   $c_j$.
   Suppose
   $Opt$ does not contain
   $c_j$, then
   $Opt=\sum _{i=0}^{j-1}count(c_i)\cdot c^i=n\ge c^j$.
   If any
   $count(c_i)\ge c$,
   $count(c_i)\cdot c^i\ge c\cdot c^i=c^{i+1}$. This would violate the optimality of
   $Opt$ since
   $count(c_i)$ number of coins could be traded for a single
   $c_{i+1}$ coin.
   
   $Opt=\sum _{i=0}^{j-1}count(c_i)\cdot c^i\le (c-1)\cdot \sum _{i=0}^{j-1}{c}^i=(c-1)\cdot \frac{c^j-1}{c-1}=c^j-1$
   A contradiction is reached. Thus
   $Opt$ must contain a
   $c_j$.

We showed that making the greedy choice

$c_j$ at every iteration leads to the optimal solution

$Opt$. This proves the greedy-choice property.

2. Optimal substructure

To prove that the greedy algorithm exhibits optimal substructure, we let

$c^j\le n<c^{j+1}(j>k\to j=k)$ and let

$Opt$ be an optimal solution.

We assume that

$Op{t}^{\prime }=Opt-\{c_j\}$ is an optimal solution for

$n-c^j$. If it were not, then

$|Op{t}^{″}|<|Op{t}^{\prime }|$ for an optimal solution

$Op{t}^{″}$. This means

$|Op{t}^{″}\cup \{c_j\}|<|Opt|$, which is a contradiction since

$Opt$ is an optimal solution.

Thus,

$Op{t}^{\prime }=Opt-\{c_j\}$ is an optimal solution for

$n-c^j$. This proves the optimal substructure property.

c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of

$n$.

• Let
  $n=10$ and
  $D=\{1,5,6\}$.
  Greedy yields
  $|\{6,1,1,1,1\}|=5$ but the optimal solution is
  $|\{5,5\}|=2$.
• Let
  $n=30$ and
  $D=\{1,10,25\}$.
  Greedy yields
  $|\{25,1,1,1,1,1\}|=6$ but the optimal solution is
  $|\{10,10,10\}|=3$.

d. Give an

$O(nk)$-time algorithm that makes change for any set of

$k$ different coin denominations, assuming that one of the coins is a penny.

// D = list of k different coin denominations

function MINIMUM-CHANGE(n,D) {
    let count = 0                      // number of coins added to change
    sort D in ascending order          // O(n) if we sort in linear time
    while n > 0                        // O(n)
        for i = D.length downto 1      // O(k)
            if D[i] <= n do
                increment count
                subtract D[i] from n
    return count
}

• $T(n)=$ sort:
  $O(n)$
  $+$ while loop:
  $O(n)$
  $\times$ for loop:
  $O(k)=O(nk)$