Introduction

• Mainly used for optimization problems
• We try to be greedy and pick up the max or min
• Applications:
  • Finding optimal solution - activity selection, fractional knapsack, prim's algo etc
  • Finding close to optimal solution for NP Hard problem like traveling salesman problem

Example:
Consider infinite supply of following value coins
10, 5, 2, 1
If someone asks for an amount how will you give the amount using minimum coins?

- maintain a set of MST
- add new vertex by adding the one with min weight (greedy)

Python

def minCoins(coins = [10, 5, 2, 1], amount):
    # greedy and pick the largest value coin first
    coins.sort(reverse=True)
    res = 0
    for x in coins:
        if x <= amount:
            c = amount // x
            res += c
            amount -= c * x
        if amount == 0:
            break
    return res

danger

It may not work always. Suppose in the example, coins=[18,1,10] and amount=20; Greedy=3 (18x1 + 1x2), but correct=2 (10x2)

General structure

def getOptimal(arr):
    res = 0
    while all items are not considered:
        i = select an item
        if i is valid:
            res = res + i
    return res