# Introduction to greedy algorithms

11 Jul 2016Greedy algorithms are good at finding solutions to problems by choosing a consistently optimal solution on each step.

## Basic concepts

- An
**optimal solution**is a feasible solution with the largest (or smallest) objective function value. - A
**local optimum**can be obtained by finding the optimal solution within a neighboring set of candidate solutions. - A
**global optimum**can be obtained by finding the optimal solutions among all possible solutions.

## Problem characteristics

**Greedy choice property**: a global optimum can be obtained by the selection of a local optimum.**Optimal substructure**: a global optimum can be obtained by using the local optimum of its subproblems.

## General strategies

### “Greedy stays ahead” arguments

Using “Greedy stays ahead” strategy, the algorithm is always at least as far ahead as the optimal solution of each iteration.

**Define your solutions.**Define what object will represent the global optimum, and what form each local optimum takes.**Find a measure.**Find a series of measurements to ensure your algorithm stays ahead of the local optimums you’ve found.**Proove greedy stays ahead.***Inductively*show that the local optimums are as good as any of the solution’s measures.*Mathematical induction:*a means of proving a theorem by showing that if it is true of any particular case, it is true of the next case in a series, and then showing that it is indeed true in one particular case.

**Prove optimality.**By*contradiction*, prove that since the algorithm stays ahead of its previous measures, it must produce an optimal solution.*Mathematical proof by contradiction:*assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove this is equivalent to assuming that That is, to assume that is true and is false.

### Exchange arguments

The greedy exchange strategy is used to prove the correctness of greedy algorithms by transforming the global optimum iteratively without worsening its quality.

**Define your solutions.**Define an object`A`

that will represent the global optimum and an object`O`

that represents a local optimum.**Compare solutions.**Show that if the global optimum is not the same as the local optimum, either:- There is an element in
`O`

that is not in`A`

. - There are two elements of
`O`

that are in a different order in`A`

. **Exchange pieces.**Gradually modify the local optimum`O`

until it is the same as the algorithm’s global optimum`A`

.**Iterate.**Decrease the number of differences between`A`

and`O`

, until you can turn`A`

into`O`

without worsening the quality of the solution. Inductively,`O`

must be optimal.

## Example: Change-making problem

This classical problem addresses the following question: How can a given amount of money be made with the least number of coins of given denominations 1, 5, 10 and 25?

Example:

```
Input:
37
Output:
4
Explanation:
37 = 25 + 10 + 1 + 1
```

Implementation in Python:

```
def change_making_problem(n):
count = 0
for coin in [25, 10, 5, 1]:
# Largest coin not greater
# than the remaining amount.
while n >= coin:
count += 1
n -= coin
return count
```