# Ch16: Greedy Algorithms
###### tags: `algorithm`
:::success
- contributed by < `TYChan6028` >
- textbook: [Introduction to Algorithms, Third Edition](https://mitpress.mit.edu/books/introduction-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 \leq 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. -- <cite>textbook, p.424</cite>

Consider the optimal way to change $d_k \leq n < d_{k+1}$ ($d_5=\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 \leq 4$ | |
| 2 | 5 | $N \leq 1$ | $1 \times 4=4$ |
| 3 | 10 | $N+D \leq 2$ | $4+5 \times 1=9$ |
| 4 | 25 | $unlimited$ | $4+10 \times 2=24$ |

As we can see from the chart, $\sum\limits_{i=1}^{k-1} count(c_i)d_i < d_k \leq 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. -- <cite>textbook, p.425</cite>

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]$

&#10233; ==$M[i]=min_{1 \leq j \leq 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 \geq 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 \leq n < c^{j+1} (j>k \rightarrow j=k)$ and the greedy algorithm returns $A=\{c_j\}+A'$ where $A$ is a solution. Let $Opt$ be an optimal solution for $n$.

1. Basis step
If $A'=\emptyset$, then $n=c^j$ and $A=\{c_j\}=Opt$.

2. Inductive step
Assume $A'=Opt' \neq \emptyset$ for $n-c^j$, then $A=\{c_j\}+A'=\{c_j\}+Opt'=Opt$.
According to our conjecture, $Opt$ must also contain a $c_j$.
Suppose $Opt$ does not contain $c_j$, then $Opt=\sum\limits_{i=0}^{j-1} count(c_i) \cdot c^i = n \geq c^j$.
If any $count(c_i) \geq c$, $count(c_i) \cdot c^i \geq 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\limits_{i=0}^{j-1} count(c_i) \cdot c^i \leq (c-1) \cdot \sum\limits_{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 \leq n < c^{j+1} (j>k \rightarrow j=k)$ and let $Opt$ be an optimal solution.

We assume that $Opt'=Opt-\{c_j\}$ is an optimal solution for $n-c^j$. If it were not, then $|Opt''| < |Opt'|$ for an optimal solution $Opt''$. This means $|Opt'' \cup \{c_j\}| < |Opt|$, which is a contradiction since $Opt$ is an optimal solution.

Thus, ==$Opt'=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)$