Greedy Algorithms

Greedy algorithms arrive at the global optimal solution by repeatedly applying the local optimal choice and then proceeding to solve the remaining optimal subproblem.

DP vs Greedy

  • Dynamic Programming (DP) solutions are bottom-up, where you build all overlapping subproblems, then the larger problem chooses the best solution from all subproblems.
  • Greedy solutions are top-down, where you choose the greedy approach without computing smaller subproblems, then you solve the single remaining subproblem.

Two Properties of Greedy Solutions

  1. Optimal Substructure: Optimal solution is constructed from optimal subsolutions within it.
  2. Greedy Choice Property: There exists an optimal solution with the greedy choice.

By induction, we can repeatedly make the greedy choice, which will leave us with smaller and smaller optimal subproblems until we solve each subproblem greedily.

Proving Correctness of Greedy Algorithms

Proving Greedy-Choice

  • Examine a globally optimal solution
  • Show that this solution can be modified such that:
    1. A greedy choice is made as the first step
    2. This choice reduces the problem to a smaller but similar problem
  • Apply induction to show a greedy choice can be used at every step

Example: In Huffman Code problem, let T be an optimal tree with:

  • a, b as nodes with max depth
  • x, y as nodes with min frequency
  • If you swap x, y with a, b ⇒ B(T’) ≤ B(T)
  • Since B(T) is optimal and B(T’) ≤ B(T) ⇒ B(T’) = B(T)
  • Therefore there exists an optimal solution with greedy choice.

Proving Optimal Substructure

Once you prove the greedy choice property, you need to prove optimal substructure.

Example: Let B(T) = B(T’) + cost(x) + cost(y) ⇒ Let’s prove B(T’) is also optimal.

  • Assume there exists B(R’) such that B(R’) < B(T’).
  • Then, B(R’) + cost(x) + cost(y) = B(R)
  • B(R’) + cost(x) + cost(y) < B(T’) + cost(x) + cost(y) = B(T).
  • B(R) < B(T) ⇒ Contradiction! Therefore B(T’) must be optimal.

Example: Assign Cookies

Problem: You are given two integer arrays:

  • greeds (of size n), where each element represents the minimum size of a cookie that a child needs to be satisfied.
  • cookies (of size m), where each element represents the size of a cookie.

You must assign cookies to children to maximize the number of satisfied children. A child is satisfied if the cookie they receive is ≥ than their greed. Each child can receive at most one cookie, and each cookie can be given to only one child.

Solution:

  1. First, sort both greeds and cookies in non-descending order.
  2. Let B(i, j) be the solution to the problem with greeds[i:n] and cookies[j:m].
  3. We have these decisions for the current child and cookie at i, j:
    • If cookie cannot satisfy child: Skip the cookie (i, j ⇒ i, j+1)
    • If cookie can satisfy child (cookies[j] ≥ greeds[i]):
      • We can either give it to current child (i, j ⇒ i+1, j+1)
      • Or we can skip this child, but why do that? We would lose a guaranteed satisfaction.
  4. We can make the argument:
    • If we have an optimal solution S(i, j) with
      • cookies[j] assigned to greeds[i+1] AND
      • cookies[j] ≥ greeds[i],
    • then we can reassign that cookie from i+1 to i, and still have an optimal solution.
    • So, an optimal solution can be converted into an optimal solution with greedy choice ⇒ we have greedy choice property!
def findContentChildren(self, g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    count = 0
    i, j = 0, 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:
            count += 1
            i, j = i+1, j+1
        else:
            j = j+1
    return count

This greedy approach works because:

  1. We sort both arrays to ensure optimal matching
  2. For each cookie, we try to satisfy the child with the smallest greed possible
  3. If a cookie can’t satisfy a child, we move on to try the next cookie
  4. This gives us the maximum number of satisfied children