LESSON 42/53Algorithm Techniques

Greedy

GOALTake the best-looking choice right now — and learn when that fails.

Greedy means: take whatever looks best right now and never look back. Sometimes that gives exactly the right answer. Sometimes it does not. Knowing which is the whole skill.

ON THIS PAGE

The example
Line by line
Watch it run
Checking whether greedy is right
Most greedy problems start with a sort
Common mistakes
Key words
Quick check
Now you try

SHOW EXAMPLE IN

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int coins(int amount, vector<int> values) {
    int used = 0;
    for (int v : values) {
        while (amount >= v) {
            amount = amount - v;
            used++;
        }
    }
    return used;
}

int main() {
    vector<int> mnt = {500, 100, 50, 10};
    cout << coins(680, mnt) << endl;

    // Greedy is NOT always right:
    vector<int> odd = {4, 3, 1};
    cout << coins(6, odd) << endl;   // greedy: 4+1+1 = 3 coins
    cout << "best is 2 (3+3)" << endl;
    return 0;
}

> what you see

6
3
best is 2 (3+3)

Try this code

//LINE BY LINE

for (int v : values) {

The values must be in order, largest first. Greedy starts from the big ones.

while (amount >= v) {

Take as many of this coin as fit, then move to the next.

cout << coins(6, odd) << endl;

With coins 4, 3, 1 greedy makes 6 as 4 + 1 + 1 — three coins. But 3 + 3 needs only two.

Watch it run

We have to make 680. The coins are listed largest first.

1 / 8

Checking whether greedy is right

Greedy is a guess, not a guarantee. Two minutes hunting for a small counterexample is far cheaper than half an hour on a wrong solution.

1.Write your rule as one sentence: "I always take the …".
2.Work three or four tiny cases by hand.
3.Actively try to build a case where the rule gives the wrong answer.
4.If you cannot find one, go ahead. If you can, you need another method.

When greedy fails, the next step is usually dynamic programming — moving from "best right now" to "account for every possibility".

Most greedy problems start with a sort

"Take the best" usually means "sort, then take from the front". The question is what to sort BY — and that choice is the whole problem.

Problem	Sort by
Хамгийн олон арга хэмжээнд оролцох / Attend the most events	Хамгийн эрт ДУУСАХААР / earliest FINISH time
Хамгийн бага зоос / Fewest coins	Хамгийн том дэвсгэртээр / largest coin first
Хамгийн бага хүлээлт / Shortest total waiting	Хамгийн богино ажлаар / shortest job first

For the events problem, sorting by START time gives the wrong answer. Only the finish time works.

//COMMON MISTAKES

✗ wrong

Шуналт арга үргэлж зөв гэж үзэх / Assuming greedy is always right

✓ right

Эсрэг жишээ хайх / Hunt for a counterexample

It works for real money but not for coins {4,3,1}. Test a few small cases by hand first.

✗ wrong

Эрэмбэлэхээ мартах / Forgetting to sort

✓ right

sort(values.rbegin(), values.rend());

Starting from the small coins makes the whole idea meaningless.

//KEY WORDS

greedy

Taking the locally best option and never reconsidering.

counterexample

One example that shows a method is wrong. One is enough.

//QUICK CHECK

Which statement about greedy is TRUE?

//NOW YOU TRY

You are given events with start and end times. Choose as many as possible without overlap. Hint: sort by EARLIEST finishing time.

Open editor

Two Pointers Backtracking

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int coins(int amount, vector<int> values) {
    int used = 0;
    for (int v : values) {
        while (amount >= v) {
            amount = amount - v;
            used++;
        }
    }
    return used;
}

int main() {
    vector<int> mnt = {500, 100, 50, 10};
    cout << coins(680, mnt) << endl;

    // Greedy is NOT always right:
    vector<int> odd = {4, 3, 1};
    cout << coins(6, odd) << endl;   // greedy: 4+1+1 = 3 coins
    cout << "best is 2 (3+3)" << endl;
    return 0;
}

> what you see

6
3
best is 2 (3+3)

Try this code

Checking whether greedy is right

Greedy is a guess, not a guarantee. Two minutes hunting for a small counterexample is far cheaper than half an hour on a wrong solution.

1.Write your rule as one sentence: "I always take the …".
2.Work three or four tiny cases by hand.
3.Actively try to build a case where the rule gives the wrong answer.
4.If you cannot find one, go ahead. If you can, you need another method.

When greedy fails, the next step is usually dynamic programming — moving from "best right now" to "account for every possibility".

Most greedy problems start with a sort

"Take the best" usually means "sort, then take from the front". The question is what to sort BY — and that choice is the whole problem.

Problem	Sort by
Хамгийн олон арга хэмжээнд оролцох / Attend the most events	Хамгийн эрт ДУУСАХААР / earliest FINISH time
Хамгийн бага зоос / Fewest coins	Хамгийн том дэвсгэртээр / largest coin first
Хамгийн бага хүлээлт / Shortest total waiting	Хамгийн богино ажлаар / shortest job first

For the events problem, sorting by START time gives the wrong answer. Only the finish time works.

//COMMON MISTAKES

✗ wrong

Шуналт арга үргэлж зөв гэж үзэх / Assuming greedy is always right

✓ right

Эсрэг жишээ хайх / Hunt for a counterexample

It works for real money but not for coins {4,3,1}. Test a few small cases by hand first.

✗ wrong

Эрэмбэлэхээ мартах / Forgetting to sort

✓ right

sort(values.rbegin(), values.rend());

Starting from the small coins makes the whole idea meaningless.

//QUICK CHECK

Which statement about greedy is TRUE?