Introduction to algorithms, greedy algorithms, some examples, and
real-world applications
What is the first thing that comes to mind when you hear the word
“greedy”? Most likely, you think of someone obsessed with wealth,
such as Mr. Krabs from Spongebob. In programming, however, one of
the most fundamental algorithm types is greedy algorithms.
An algorithm is a specific set of instructions/steps used to
accomplish a task. Greedy algorithms are defined as any
algorithm that determines the solution to a problem by taking the
locally optimal choice at every sub-problem of the problem
(hence the name greedy- they’re always taking whatever they can at
the moment without considering the future).
Example: Your house is on fire, and you want to bring the most
valuable items outside, but you only have time to enter and exit the
house 4 times before it collapses (for a total of 8 items carried
outside). By taking the 2 most valuable items in the house every
time you enter (every entrance to the house is the sub-problem, and
taking the 2 most valuable items is the locally optimal choice for
that sub-problem), in the end, you will have the 8 most valuable
items outside. This is the globally optimal solution.
In the example, using a greedy algorithm produces the globally
optimal solution. However, a lot of real-world applications of
greedy algorithms do not produce the globally optimal solution.
Instead, they are used to provide an approximate solution because
determining the exact solution takes far longer. Discussion of these
applications is outside of the scope of this article, but if you are
interested, some common examples of greedy algorithms are the
traveling salesman problem, vertex cover, k-center clustering (not
to be confused with k-means clustering), and gradient descent.
Let’s take a look at some examples with code.
Example 1
Problem: Given an array of positive integers, determine the maximum
sum of 3 elements in the array.
Solution:
Determine the largest element, add it to the sum. Remove the
element.
Determine the largest element, add it to the sum. Remove the
element.
Determine the largest element, add it to the sum.
Sub-problems: Finding the largest element in the array
At each step, we can take the locally optimal solution
(finding the largest element), then add it to the sum. In the end,
we have the globally optimal solution of the maximum sum of 3
elements in the array
Implementation of the solution:
Code:
arr = [4, 6, 2, 8, 13, 11]
sum = 0
# step 1
sum += max(arr)
arr.remove(max(arr))
# step 2
sum += max(arr)
arr.remove(max(arr))
# step 3
sum += max(arr)
# verify our results
print("Maximum sum: " + str(sum))
Instead of removing the element, we can set it equal to -1 which
has the same effect.
Code:
int arr[] = {4, 6, 2, 8, 13, 11};
int sum = 0;
// step 1
int mx = arr[0], mxidx = 0;
for(int i = 1; i < (sizeof(arr)/sizeof(*arr)); i++) {
if(arr[i] > mx) {
mx = arr[i];
mxidx = i;
}
}
sum += mx;
arr[mxidx] = -1;
// step 2
mx = arr[0];
mxidx = 0;
for(int i = 1; i < (sizeof(arr)/sizeof(*arr)); i++) {
if(arr[i] > mx) {
mx = arr[i];
mxidx = i;
}
}
sum += mx;
arr[mxidx] = -1;
// step 3
mx = arr[0];
mxidx = 0;
for(int i = 1; i < (sizeof(arr)/sizeof(*arr)); i++) {
if(arr[i] > mx) {
mx = arr[i];
mxidx = i;
}
}
sum += mx;
// verify our results
cout << "Maximum sum: " << sum;
Output:
> Maximum sum: 32
Instead of removing the element, we can set it equal to -1 which
has the same effect.
Example 2
Problem: You are working at a company where, in return for doing
task A, you are given
B
dollars. At the beginning of the week, you receive
N
requests for task A. However, task A can also be customized
according to the customer’s needs (although you are always paid
B
dollars), and for each of the
N
requests, the
i
-th request will take
Ti
hours to complete. Given you work
W
hours on requests of task A throughout the week, what is the maximum
number of dollars you can earn that week from task A?
Solution: Sort the tasks by the time
Ti
it will take to complete the task. Then, greedily complete each task
starting with the shortest tasks until the
W
hours are over.
Sub-problems: Identifying the task that will take the shortest
amount of time.
At each step, we can take the locally optimal solution
(finding the shortest task), then add it to the total time spent. In
the end, we have the globally optimal solution of the maximum
number of dollars you can earn that week from task A.
Implementation of the solution:
Code:
B = 20
N = 8
W = 30
T = [2, 7, 30, 14, 8, 4, 10, 6]
T.sort()
passedTime = 0
idx = 0
while passedTime + T[idx] <= W and idx < N:
passedTime += T[idx]
idx += 1
print("Total dollars earned: " + str(B*idx))
Output:
> Total dollars earned: 100
Code:
int B = 20;
int N = 8;
int W = 30;
int[] T = {2, 7, 30, 14, 8, 4, 10, 6};
Arrays.sort(T);
int passedTime = 0;
int idx = 0;
while(passedTime + T[idx] <= W && idx < N) {
passedTime += T[idx];
idx++;
}
System.out.println("Total dollars earned: " + B*idx);
Output:
> Total dollars earned: 100
Code:
int B = 20;
int N = 8;
int W = 30;
int T[] = {2, 7, 30, 14, 8, 4, 10, 6};
sort(T, T+N);
int passedTime = 0;
int idx = 0;
while(passedTime + T[idx] <= W && idx < N) {
passedTime += T[idx];
idx++;
}
cout << "Total dollars earned: " << B*idx;
Output:
> Total dollars earned: 100
(Note in this case 1 represents true)
Greedy algorithms as a whole are an incredibly broad topic. There is
no silver bullet for creating greedy algorithms. The most important
characteristic to remember when solving greedy problems is “how do
locally optimal solutions contribute to a globally optimal result.”
You can play with all the code we've used in this article on Replit: