Greedy

8pts

Python

Java

C++

Algorithms

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))
```

Output:
> Maximum sum: 32

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 < arr.length; 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 < arr.length; 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 < arr.length; i++) {
if(arr[i] > mx) {
mx = arr[i];
mxidx = i;
}
}
sum += mx;
// verify our results
System.out.println("Maximum sum: " + sum);
```

Output:
> Maximum sum: 32

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 T_{i}

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

T_{i}

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:

Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!

Copyright ©2021 Howard County Hour of Code

Copyright ©2021 Howard County Hour of Code