# Greedy Algorithm: Optimal Substructure

I don't have a CS degree but I have recently taken up studying algorithms very seriously.

I have been studying greedy and dynamic programming for days and I come across the below definition a lot, seems they all come from the same source, but I do not understand what it means, it is one of the vaguest definitions I have ever come across. I wonder if someone can please help me explain this.

e.g. I don't understand what they mean by optimal solution, what constitutes an optimal solution, how can I define it?

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem

Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.

To answer your question, let's look at a simple example, change-making problem:

Given a set of integer values of coins $$C = \{c_1, …, c_n\}$$ and an amount $$W$$, what is the minimum number of coins to add-up to the amount $$W$$?

The classical greedy approach is the following:

While W > 0
pick the largest coin c that is <= W
W <- W - c


For example, with $$C = \{1, 2, 5\}$$ and $$W = 13$$, you will pick $$5$$, $$5$$, $$2$$ and $$1$$, and you can show that the minimum number of coins required is indeed $$4$$.

However, this algorithm does not always provide an optimal solution. For example, if $$C = \{1, 4, 5\}$$ and $$W = 8$$, the greedy algorithm will choose coins $$5, 1, 1, 1$$ when there is a solution $$4, 4$$ using less coins.

Back to the topic of your question, the change-making problem does not have an optimal substructure, unless you add some hypotheses on $$C$$

• Thanks for the answer, it makes a lot of sense, but I have a follow-up question, does this mean that it is not advisable to use the greedy algorithm? because from the above example, it is almost impossible to know if you will have an optimal substructure, unless you already know the input May 23 at 20:13
• It is not always a bad idea to use a greedy algorithm. The reasons are: 1) they are generally simple to implement 2) some of them are optimal and it is not that hard to prove (e.g. Kruskal, Prim, Dijkstra, interval schedulling, …) 3) some of them have way better time complexity than (known) optimal algorithms and still provide "good" solutions (e.g. graph coloring, subset sum, …) May 23 at 20:18

Usually, in the context of dynamic programming and optimization methods, we are interested in problems where we have to "find" some value which maximizes \ minimizes a certain function.

For example, take the following problem: You are a cashier in a shop, and a customer gave you an $$n$$-dollar bill (your country has bills of all kinds! very intriguing), for an item that costs only $$k dollars, and you want to give the customer correct change. However, your cashing station has only limited amount of bills of each type, and this information is given to you in a list with tuples of the form (dollar value, number of dollars in cashing station). But, you also want to keep the number of bills in your station as large as possible, so you could give change to other customers as well.

In this problem, a "solution" would be a way to give change to the customer, and an "optimal solution" is a solution that also keeps as many bills as possible in the station

• Apparently this answer is the same as @Nathaniel's answer. We both answered with the same solution (without talking with each other), what a nice coincidence! :) May 23 at 20:17

Check e.g. Jeff Erickson's Algorithms (warning, somewhat though going), it has a thorough chapter on greedy algorithms. He also warns that greedy algorithms very rarely give optimal results (The underlying problem has to have a very particular structure for them to work in all cases, see e.g. Jeremy Kun's "When Greedy Algorithms are Perfect". Sure, several very important algorithms are greedy algorithms.).

Greedy algorithms are attractive as a way to get approximate solutions, as they are usually simple to code and very fast, and they sometimes get good solutions (can be proved are within some reasonable factor of the optimal solution).