Proving a greedy rule in Python, and when greedy fails

Why this lesson matters

A greedy rule that passes your three test cases can still be wrong. That is the most common trap in this topic. You write a sort, a loop and a sensible-looking rule, you check it on the example in the question, and it gives the right number. Then a case you did not think of gives a wrong number, and nobody notices until the test fails or the interviewer asks a follow-up question.

In an interview, "it looks right" is not an answer. You need a short argument that the rule is safe, and you need a sense of which problems are not safe for greedy. This lesson gives you both. It also gives you two tools that work in any language: a testing method that compares a rule with brute force on many small inputs, and a checklist to run before you trust a rule.

By the end of this lesson you will be able to write an exchange argument for activity selection and for fractional knapsack, explain why coin change and 0/1 knapsack break greedy with concrete counterexamples, and check any rule with a randomised test in Python.

What a proof means here

A proof is an argument that a claim is true for every input, not just the ones you tested. For a greedy rule, the claim is: "following this rule always gives a best answer." You cannot test every input, because there are too many. You can, however, show that every step of the rule keeps the best answer possible.

The argument uses two properties. Most greedy problems that work have both.

1. The greedy choice property. There is always some best answer that starts with the greedy choice. Put plainly: the rule never makes you give up the best answer on the first step.
2. Optimal substructure. After making the greedy choice, what is left is a smaller problem of the same kind. If you solve that smaller problem optimally, and add the greedy choice back, you get an optimal answer for the whole problem.

Together these two properties let you repeat the argument: take the greedy choice, shrink the problem, and apply the same reasoning again. When the problem is empty, you have a best answer.

The exchange argument

The most common way to prove the greedy choice property is the exchange argument. The steps are always the same.

1. Take any best answer, called an optimal solution. Assume it does not use the greedy choice.
2. Swap one of its choices for the greedy choice.
3. Show that the swapped answer is still valid, and that it is no worse than the original.
4. Conclude that a best answer exists that uses the greedy choice. Then repeat the argument on the smaller problem that remains.

The word "exchange" means swap. You are not proving that greedy is always the best. You are proving that you can always swap in the greedy choice without losing anything. That is enough.

A physical picture helps. Imagine a relay race. The team has a best order of runners. If you can take the first runner and swap in a faster one without breaking the handoffs, the team is no worse off. The swap only needs to keep the race legal and not slow the team down.

Activity selection, proved in full

Let us prove that sorting by end time is correct. Here is the claim: there is always a best set of meetings whose first meeting, in time order, is the one that ends earliest among all meetings. Call that meeting g.

Start with any best set S, which is a largest set of non-overlapping meetings. If S is empty, the room has no meetings at all, which can only happen if the input is empty. In that case there is nothing to prove. Otherwise, let f be the first meeting in S in time order. Since g ends earliest of all meetings, the end of g is at most the end of f.

Now form a new set S2 by removing f and adding g. Is S2 valid? The other meetings in S are not f, and each one starts at or after the end of f, because f is the first meeting in time order. Since the end of g is at most the end of f, each of these meetings also starts at or after the end of g. So none of them overlaps g. The set S2 is valid.

Does S2 have the same size as S? Yes. We removed one meeting and added one. So S2 is also a best set, and it starts with g. The greedy choice is safe.

Now the second part, optimal substructure. Once g is chosen, the remaining problem is to choose the largest set of meetings that start at or after the end of g. The rest of S2 is such a set, and it is best possible for that smaller problem. Why? If there were a larger set of meetings starting after the end of g, adding g to it would give a valid set larger than S2, which would contradict that S2 is best. So the smaller problem is solved optimally by whatever greedy does next. Greedy then repeats the same choice on the smaller problem: take the meeting that ends earliest among those that start at or after the end of g. The argument applies again, and so on until nothing is left.

This proof explains every line of the greedy code. The sort puts g first. The check start >= last_end keeps only meetings that start after the last chosen end. The loop is the repeated smaller problem.

Interviewers like a version of this proof in three or four sentences. Here is one: "Let g be the meeting that ends earliest. Any best schedule can swap its first meeting for g, because g ends no later and so cannot clash with the rest. The swapped schedule has the same size, so g is safe to take. The remaining meetings form the same problem on a shorter timeline, so the argument repeats."

Fractional knapsack, in three sentences

Lesson 2 gave the rule for the fractional knapsack: take items by value per unit of weight, highest first. The exchange argument for it is short. Take any best bag. If it holds less of the highest-ratio item than it could, find a unit of some other item in the bag and swap it for a unit of the highest-ratio item, keeping the total weight the same. The swap changes the value by the ratio difference times the weight swapped, which is zero or positive, so the new bag is no worse. Repeating this moves the bag toward the greedy fill, which means greedy is best.

The swap works here because items can be split. You can exchange any amount of one item for an equal amount of weight of another. Whole items cannot be exchanged this way, and that difference is the whole story of the next sections.

Two properties in action: the job rule

The job sequencing rule from lesson 2 also has a short exchange argument. Sort by profit, highest first. Take the highest-profit job j. Suppose a best schedule does not include j. If j can fit in some free hour, add it, which only raises the profit. If no hour is free before its deadline, some job k occupies an hour that j could use. Remove k and put j in its place. Since j has at least as much profit as k, the profit does not drop. So a best schedule exists that includes j. Latest-free placement is a separate argument about keeping early hours free, and that matters for the slot search, not for the choice of which jobs to take.

Notice how the same pattern keeps appearing. The greedy choice is the largest or smallest item under some key. The exchange swaps that item into the best answer. The argument says the swap does not hurt. Practise writing this in your own words for each problem you study.

When greedy fails: coin change with unusual coins

Now the other side. Here is a problem where the greedy rule is wrong. You want to pay an amount using the fewest coins. The greedy rule takes the largest coin that fits, again and again. For the coins 25, 10, 5 and 1, the rule is correct. For other coin sets, it can fail.

Take the coins 4, 3 and 1, and the amount 6. Greedy takes 4 first, which leaves 2. Two left is two 1s, so greedy uses three coins: 4 + 1 + 1. But 3 + 3 uses only two coins. Taking the biggest coin first blocked the best answer.

The picture below shows both ways of paying 6.

Amount 6 with coins 4, 3 and 1: greedy uses 4, 1, 1 for three coins, while the best uses 3 and 3 for two coins

The right tool for a coin problem with any coin set is dynamic programming, which module 26 covers. The idea is to build a table of the best answer for every amount from 0 up to the target. Each entry uses the entries before it. The next visualizer shows the table for the coins 4, 3 and 1, filled in one amount at a time. Watch how each cell looks back at a few earlier cells and takes the smallest.

For amount 6, the table shows the value 2. The cell for 6 looks back at the cell for 2 (with coin 4) and the cell for 3 (with coin 3). Cell 3 has value 1, so 6 gets 1 + 1 = 2 from coin 3, which is 3 + 3. The table keeps all the answers, so it never has to commit early to a choice that might be wrong.

The program below does both: it runs the greedy rule and the table method, and prints each amount where they disagree between 1 and 10. The table method is the reference answer. A greedy rule is only correct if it matches the reference for every amount you care about. The table starts with math.inf for the amounts not yet known. math.inf stands for infinity. It is larger than any number, so min ignores it.

No input is needed. Press Run.

Output:

amount 6: greedy 3, best 2
amount 10: greedy 4, best 3
done

Two amounts disagree. For 6, greedy uses 4 + 1 + 1 and the best is 3 + 3. For 10, greedy uses 4 + 4 + 1 + 1, which is four coins, and the best is 4 + 3 + 3, which is three coins. The amounts 1 to 5, 7, 8 and 9 agree, which is exactly why a few small tests can be misleading. Greedy looked right for many amounts, and then failed at 6.

Read the best function carefully. table[a] is the fewest coins for the amount a. For each coin that fits, it considers paying coin now and then the best answer for a - coin. It keeps the smallest total. Every cell is computed from earlier cells, so the table is complete when the loop ends. This is dynamic programming in its simplest form, and it runs in O(target * coins) time.

When greedy fails: 0/1 knapsack

The second famous failure is the 0/1 knapsack. It looks almost the same as the fractional knapsack, but each item must be taken whole or left out. You cannot take part of an item.

Use the same three items as before: value 60 and weight 10, value 100 and weight 20, value 120 and weight 30. The capacity is 50. Sorted by ratio, the order is the same, and the greedy rule takes the first two items, which weigh 30 together and are worth 160. The third item weighs 30, and only 20 units are left, so it does not fit. The greedy total is 160.

But the best choice of whole items is items 2 and 3, which weigh 50 together and are worth 220. The greedy rule gave up the best answer on its first choice, because the first item used up room that could have held a better combination.

The fractional knapsack gives 240, because it can take two thirds of the third item. The whole-item version cannot, so 240 is out of reach. This gap is why the exchange argument from the fractional case breaks. You cannot swap half of one item for half of another and keep the value exact, so the swap that proved the fractional rule does not work.

The next program checks every subset of items, which is the brute-force method, and compares it with the greedy rule for whole items. Brute force is slow for large inputs, but it is always correct. For six items it checks 64 subsets, and that is enough to be sure.

No input is needed. Press Run.

Output:

best whole-item value: 220 (mask 6)
greedy by ratio:       160

The mask is a number whose bits say which items are in the subset. Mask 6 is binary 110, which means items 2 and 3, the ones with bit 1 and bit 2 set. The expression (mask >> i) & 1 gives 1 when bit i of the mask is set, and 0 when it is not. Brute force uses this trick to list every subset without writing nested loops.

The two answers differ, and the greedy answer is smaller. The lesson is simple. Greedy by ratio is correct for the fractional knapsack and wrong for the whole-item knapsack. The same sort key is correct in one problem and wrong in another, so the problem statement decides the rule.

The standard way to solve the 0/1 knapsack is dynamic programming, in module 26. It builds a table over items and capacities, and it does not commit to any early choice.

The checklist before you trust a rule

Before you rely on a greedy rule, go through these questions. Each one catches a common mistake.

• Can I state the rule in one sentence?
• Can I write the exchange argument in a few lines?
• Can I find a small counterexample? Try three or four items with unusual values, especially a short item that sits in the middle of two long ones.
• Does the problem allow parts of an item, or only whole items? The answer changes the rule.
• Does the sort give a clear order, or can ties change the answer? If ties matter, decide how to break them.
• Have I tested the rule against brute force on many small inputs, not just the example?

The last question is the one most people skip. The next section shows how to do it in code.

Testing a rule against brute force

Brute force is a slow method that checks every option. For small inputs it is correct, so it can serve as a judge. The testing method is simple. Generate many small random inputs. For each input, run the brute force and the greedy rule. Count the disagreements. If the rule never disagrees, it passes the test. If it disagrees once, it is wrong, and the disagreeing input is the counterexample you need.

The next program runs this test for activity selection with two rules. The random numbers come from the random module with a fixed seed, so the same 300 cases appear on every run. rng.randrange(6) returns a whole number from 0 to 5. A fixed seed is a deliberate choice. It makes the test repeatable, so a failure can be reproduced. The key argument of sorted takes a function that returns the value to sort by. Each rule is one such function.

No input is needed. Press Run.

Output:

earliest end:   0 wrong out of 300
shortest first: 99 wrong out of 300
first shortest-first failure: [(2, 6), (0, 1), (8, 9)] best is 3

The earliest-end rule was wrong in 0 of 300 cases, which is strong evidence, combined with the proof in this lesson. The shortest-first rule was wrong in 99 of 300, which is a clear failure. The first counterexample is a list of three meetings. The two shortest meetings both have length 1, namely (0, 1) and (8, 9). Shortest-first takes both, which ends at 9. The long meeting (2, 6) is checked last, and it starts at 2, which is before 9, so it is skipped. The count is 2. The best is 3, from (0, 1), (2, 6) and (8, 9), which do not overlap. The rule chose the short meetings first and never got back to the long one that would have fit.

This test is cheap to write, and it catches mistakes that a textbook example misses. In an interview you can describe it in one sentence: "I would check the rule against a brute force on random small inputs before I trust it." That sentence shows that you know how to test a rule.

A caution. Random tests only check the inputs they generate. A passing test does not prove a rule is correct. The proof does that. Use the test to find a counterexample quickly, and use the proof to be sure when the test finds none.

A subtle Python trap: is and ==

Greedy code often compares numbers, for example to check whether two values are equal. In Python, == compares values. The is operator compares identity, which means whether two names point to the same object. For small integers, CPython, the standard Python program, reuses one shared object, so is happens to give the right answer for them. Larger numbers can be separate objects, so is can say False even when the values are equal. The next program shows the difference.

No input is needed. Press Run.

Output:

127 is 127:    True
1000 is 1000:  False
1000 == 1000:  True
literal 1000 is 1000 in one file: True

The first line is true only because of the shared object for small numbers, which is an accident of the value. The second line is false, even though the numbers are equal. The third line shows the fix for equality: use ==. The last line is the surprise. In one file, the compiler can merge two identical number literals into one object, so is says True. The result depends on how the code was written, so do not use is to compare numbers. Use ==, or < and > for order. The sort functions and heapq use < for you, so the trap appears only when you write is by hand. If you know Java, is is close to Java's == on objects, which is the same kind of trap.

This bug is silent. The program runs, the output looks plausible, and only some inputs trigger it. It is one of the most common errors in code reviews.

Shortest paths with negative edges

Dijkstra's algorithm, which finds shortest paths in a graph, is also a greedy algorithm. At each step it finalises the closest vertex that has not been finalised yet. This works only when all edge weights are zero or positive. A negative edge can break the greedy choice, because a path through a negative edge can be shorter than one that was already finalised.

Here is a three-vertex example in words. There is a start vertex S, a vertex A and a vertex B. The edge from S to A costs 1. The edge from S to B costs 2. The edge from B to A costs negative 5. The true shortest path from S to A goes through B: 2 + (-5) = -3.

Dijkstra first finalises A with cost 1, because it is the closest vertex. Later it reaches B with cost 2 and sees the negative edge to A. But A is already finalised, so the algorithm does not update it. The answer for A stays at 1, which is wrong.

S -> A costs 1
S -> B costs 2
B -> A costs -5
true shortest cost to A: 2 + (-5) = -3
Dijkstra's answer for A: 1 (wrong, because A was finalised too early)

The fix is a different algorithm, such as Bellman-Ford, which handles negative edges by checking every edge several times. The lesson for this module is that a greedy finalisation step is safe only when no later choice can make an earlier one worse. A negative edge is exactly a later choice that can do that.

A concrete exchange on real numbers

The abstract argument is easier to trust after you see a swap on actual numbers. Take the eleven-meeting set from lesson 1. Its best answer is (1,4), (5,7), (8,11), (12,16), which has 4 meetings. The greedy rule starts with (1,4), the meeting that ends earliest.

Now take a different best answer that does not start with the greedy choice: (3,5), (5,7), (8,11), (12,16). It also has 4 meetings, and it is valid. Its first meeting is (3,5), which ends at 5. The greedy meeting (1,4) ends at 4, which is no later.

Step 2 is the swap. Remove (3,5) and add (1,4). The new set is (1,4), (5,7), (8,11), (12,16).

Step 3 checks validity. The meeting (1,4) ends at 4. The next meeting, (5,7), starts at 5, which is after 4, so there is no clash. The rest of the set did not change, and each of those meetings still starts after the first one ends. So the swapped set is valid.

Step 4 checks the value. The count is still 4, so nothing was lost. The swap moved the first meeting earlier in time, and an earlier end never blocks more of the future.

Step 5 repeats on the rest. The remaining meetings must start at or after 4. Among them, the earliest-ending meeting is (5,7), and the same kind of swap applies. Repeating the step gives the greedy schedule.

This is the whole method on a real case. The swap always keeps the set valid, because the greedy meeting ends no later than the one it replaces. That single fact is what the proof rests on.

Writing the exchange argument for your own rule

When you meet a new problem, you may need to write your own exchange argument. A repeatable plan helps. Follow the steps in order, and write each one as a sentence before you move on.

First, write the rule. It should name one item, the greedy choice, that the rule picks. For example: "pick the item with the largest value per unit of weight."

Second, take a best answer that does not contain the greedy choice. Say what the best answer is, using the words of the problem. For example: "Let B be a best bag. Suppose B does not contain all of the highest-ratio item."

Third, describe the swap. Name the item you remove from the best answer and the greedy item you add in its place. Say what the swap keeps fixed, such as the total weight or the number of meetings.

Fourth, check validity. Show that the new answer still satisfies every constraint. For intervals, that means no overlaps. For a bag, that means the total weight is at most the capacity. For jobs, that means each job fits in an hour no later than its deadline.

Fifth, check the value. Show that the swapped answer is no worse. Use the sort order: the greedy item is at least as good as the item it replaces, under the sort key.

Sixth, repeat on the rest. Say why the remaining problem has the same form, so the argument applies again.

If you cannot finish step five, the rule is probably wrong. Go back to brute force and look for a counterexample. The swap that fails is often the counterexample itself, so the two methods support each other.

Greedy problems, dynamic programming problems: how to tell

Greedy and dynamic programming both solve optimisation problems, and they look similar on the surface. A few signals help you choose.

• If the problem asks for the best set of things under a simple sort key, with a clear exchange argument, try greedy.
• If the problem asks for the number of ways, or the best total over a sequence of choices where each choice depends on earlier ones, try dynamic programming.
• If a greedy rule works on your small tests but fails on a counterexample you find with brute force, you need dynamic programming or a different structure.
• If the items cannot be split, be extra careful. Many greedy rules that work for fractions fail for whole items.

The rule of thumb is not perfect. It is a starting point. The proof and the counterexample are the real tests.

Common mistakes and their real messages

Trusting a rule because the example passed. This is the central mistake of the topic. The fix is the two-step habit: find a small counterexample with brute force, then write the exchange argument.

Choosing the key without testing the alternatives. Start time, length and end time all look reasonable. Only end time is safe for activity selection, and the random test above shows how often shortest-first fails. Test each key before you choose one.

Using greedy coin change for any coin set. It works for coins like 25, 10, 5 and 1, but it fails for 4, 3 and 1. Ask whether the coin set is special before you trust greedy.

Using greedy for the 0/1 knapsack. The fractional rule gives 240 and the whole-item answer is 220. A greedy whole-item rule gives 160. Use dynamic programming for whole items.

Comparing numbers with is. The output looks right for small values and wrong for large ones. Python gives no error, so it is a silent wrong answer. Check every comparison in a sort key or a condition, and use == for equal values.

Assuming ties do not matter. In activity selection, ties in end time do not change the count, because the proof holds for any tie-break. Ties can still change the chosen list, so decide on a tie-break and test it. In the shortest-first rule, the order of equal lengths can change the list too, so a rule that depends on ties is fragile.

Forgetting the sort. A greedy rule without a sort is just a loop over the input in its given order, and that is not greedy in the useful sense. Print the sorted order during debugging to confirm it. sorted(items, key=...) returns a new list, while items.sort(key=...) changes the list in place. Both work, but a call to sorted whose result is thrown away does nothing.

Debugging walkthrough: finding a counterexample

When you think a greedy rule might be wrong, follow these steps.

1. Write the rule in one sentence. If you cannot, the rule is not clear enough to test.
2. Pick the smallest input that could break it. For intervals, three or four items. For coins, a small amount.
3. Compute the brute force answer by hand or with a short program.
4. Run the greedy rule on the same input and compare.
5. If they differ, you have a counterexample, and the rule is wrong. If they agree, try a few more inputs that look unusual.
6. If many small inputs agree, write the exchange argument. If the argument goes through, the rule is safe.

The randomised test automates steps 2 to 5. It is the most useful habit in this lesson, because it finds mistakes that you would never think of by hand.

Interview questions you should be ready for

1. How would you prove a greedy rule is correct? Use the exchange argument. Take a best solution that does not use the greedy choice, swap in the greedy choice, and show the result is still valid and no worse. Then argue that the rest is the same problem on a smaller input.
2. Why does greedy fail for the 0/1 knapsack? Because items cannot be split, so the exchange argument breaks. The highest-ratio item can use room that a better combination of other items needed.
3. Give a coin set where greedy fails. Coins 4, 3 and 1 for the amount 6. Greedy gives three coins, and the best is two.
4. Why does Dijkstra fail with a negative edge? It finalises a vertex too early. A later path through a negative edge can be cheaper, and the finalised vertex cannot change.
5. How would you check a rule quickly before you code it? Write a brute force for small inputs and compare with the rule on random cases. Then write the exchange argument.

Real-world uses

Proofs like this one are what engineers rely on when a simple rule is used in production. The rule that picks the next job, route or request must be safe for every input the system might see, not just the ones on a whiteboard. A failing randomised test is often the cheapest way to catch a bad rule before it reaches users.

The coin change example also matters in practice. Some currencies and some payment systems do not use canonical coin sets, and a greedy cashier can use more coins than necessary. Checking the coin set against a table method is a practical safety step.

Summary of this module

• A greedy algorithm repeats a locally best choice and never undoes it.
• Activity selection sorts by end time. Fractional knapsack sorts by value per unit of weight. Job sequencing sorts by profit and places each job in the latest free hour.
• Huffman coding merges the two smallest frequencies with a min-heap from heapq.
• The exchange argument proves a greedy choice is safe. It swaps the greedy choice into a best answer and checks that nothing gets worse.
• Greedy fails for coin change with unusual coins, for the 0/1 knapsack, and for shortest paths with negative edges.
• Test any rule against brute force on small random inputs before you trust it.

Practice

1. Find a coin set and an amount where greedy needs more coins than the best answer. Hint: coins 1, 5 and 6 with amount 10.

Show the answer

Use coins 1, 5 and 6, with amount 10. Greedy takes 6 first, which leaves 4, and then four 1s. That is five coins. The best is 5 and 5, which is two coins.

2. Write the exchange argument for the fractional knapsack in three sentences. Use the words "swap", "ratio" and "weight".

Show the answer

Take any best bag. If it holds less of the highest-ratio item than it could, swap some weight of a lower-ratio item for the same weight of that item, which keeps the total weight the same. The value changes by the ratio difference times the weight swapped, which is zero or positive, so the new bag is no worse. Repeating the swap until the bag is filled by ratio shows that greedy is best.

3. Why does the 0/1 knapsack break the greedy proof? Give one sentence that uses the word "exchange".

Show the answer

Whole items cannot be swapped by a fraction, so the exchange cannot keep the total weight exact, and the swapped answer may be smaller or may not fit. With items 2 and 3 of the earlier example, the highest-ratio item uses room that the best pair needed.

4. A friend says: "I tested the rule on the example and it worked, so it is correct." Write a reply in four sentences that explains what is missing.

Show the answer

A rule that works on one example can still fail on another input, because the example may not contain the tricky case. The missing step is a counterexample search, such as a brute force on small random inputs. The missing argument is an exchange proof, which shows the rule works for every input.

5. Modify the random test so it uses 1000 cases and a seed of 99. Predict whether the earliest-end rule still has zero mismatches, and explain your reasoning.

Show the answer

The earliest-end rule should still have zero mismatches, because the exchange argument proves it for every input, and the random test is only a check. The number of cases changes the sample, not the truth. A different seed gives different cases, but the proof does not depend on the seed.

6. For the input (0,3), (2,5), (4,7), find the best count by hand. Then check whether shortest-first gets it right.

Show the answer

Sorted by end: (0,3), (2,5), (4,7). Take (0,3). Skip (2,5), which starts at 2 before 3. Take (4,7). The best count is 2. Shortest-first sorts by length: all three have length 3, so the order is the input order, (0,3), (2,5), (4,7). The rule takes (0,3) and gets the right answer here, which is a case where the wrong rule passes by luck.

7. Explain why the table method for coin change is slower than greedy but always correct.

Show the answer

The table method computes the best answer for every amount up to the target, and each entry looks at a few earlier entries, so it never commits to a choice too early. Greedy does one pass, which is faster but can commit to a wrong coin. The table costs O(target * coins) time, which is slower for large amounts but always correct.

8. Build a three-vertex graph where Dijkstra gives a wrong answer. Use the vertices S, A and B, with a negative edge.

Show the answer

Use vertices S, A and B, with edges S to A of cost 1, S to B of cost 2 and B to A of cost negative 5. Dijkstra finalises A with cost 1 before it sees the negative edge, so it reports 1 for A. The true cost is negative 3, through B.

9. A rule picks the item with the largest value first for the 0/1 knapsack. Find an item set where this gives a smaller answer than the best. Hint: use one heavy item of value 100 and weight 50, and two items of value 60 and weight 25 each, with capacity 50.

Show the answer

Take the heavy item (value 100, weight 50) with the largest value first. It fills the bag at 100. The best is the two items of value 60 and weight 25 each, which total 120 and weigh exactly 50. So the largest-value rule gives 100 and the best is 120.

10. Explain why c is d printed False in the program, even though c == d printed True.

Show the answer

c and d are two separate int objects, because 1000 is outside the small range that CPython shares, which is from -5 to 256. The is operator compares the object identity, so it says False. The == operator compares the numeric values, so it says True.

What you now know

• A greedy rule needs a proof, usually an exchange argument, and a test against brute force.
• The exchange argument swaps the greedy choice into a best answer and checks that nothing gets worse.
• Greedy fails for coin change with coins such as 4, 3 and 1, for the whole-item knapsack, and for shortest paths with negative edges.
• Dynamic programming, in module 26, solves the problems where greedy fails.
• Compare numbers with ==, < and >, never with is.

Next lesson: the module assignment, where you combine these tools in one program.