Greedy Algorithms

Overview

approach for solving problem by selecting best option available
- doesn't worry whether current best result will bring overall optimal result
- never reverses earlier decision
- works in top-down approach
may not produce best result for all problems because it always goes for local best choice to produce global best result
greedy algorithms are a good fit for problems with following properties
1. greedy choice property: optimal solution to problem can be found by choosing best choice at each step without reconsidering previous steps
2. optimal substructure: optimal overall solution to problem corresponds to optimal solution to its subproblems

Advantages of Greedy Approach

easier to describe
can perform better than other algorithms (though not in every case)

Drawback of Greedy Approach

major disadvantage is that it doesn't always produce optimal and/or feasible solution

Definition/Steps

start with empty solution set
at each StereoPannerNode, item added to solution set until solution is reached
if solution set is feasible, current item is kept
else, item is rejected and never considered again

Example

Problem

For a given amount of money, make change using the fewest possible number of coins.

Available coins are

$5 coin
$2 coin
$1 coin

There is no limit to the number of each coin you can use.

Solution

def greedy_make_change(amount):
    solution_set = dict(_5=0, _2=0, _1=0, change_sum=0)
    coins = [5, 2, 1]

    while solution_set["change_sum"] < amount:
        for coin in coins:
            if solution_set["change_sum"] + coin <= amount:
                coin_key = f"_{coin}"
                solution_set[coin_key] += 1
                solution_set["change_sum"] += coin
                break

    return solution_set

Different Types of Greed Algorithms

Made with