Back to blog# Greedy Algorithm: Solving the Boats to Save People Problem

Published on Apr 04 2023

Last updated on Apr 06 2023

No translation available.

Add translationThe Greedy Algorithm is a simple yet powerful technique used to solve optimization problems in computer science and programming, enabling computers to perform complex tasks efficiently. In this blog post, we will explain what a Greedy Algorithm is, how it works, and use it to solve the Boats to Save People problem, while also comparing its time complexity to a for loop approach.

A Greedy Algorithm is a simple algorithmic technique used to solve optimization problems. The basic idea behind this algorithm is to make the locally optimal choice at each step with the hope of finding a global optimum. In other words, a Greedy Algorithm always chooses the next best option, without worrying about the future consequences. It assumes that the best solution can be obtained by making the locally optimal choice at each step.

For example, consider a scenario where you are trying to find the shortest path from one point to another. A Greedy Algorithm would choose the path that is closest to the destination at each step until it reaches the final destination. This may not always result in the absolute shortest path, but it is a quick and efficient way of finding a relatively short path.

Simplicity: The Greedy Algorithm is a simple algorithmic technique, making it easy to understand and implement.

Efficiency: In many cases, the Greedy Algorithm is a very efficient way of solving optimization problems. It has a time complexity of O(n log n) in most cases, making it faster than brute force algorithms.

Flexibility: The Greedy Algorithm can be used to solve a wide range of problems, including problems in computer science, operations research, and engineering.

Suboptimality: The Greedy Algorithm makes locally optimal choices at each step, without considering the future consequences. Therefore, it may not always lead to the globally optimal solution.

Limited Applicability: The Greedy Algorithm is only suitable for solving problems that exhibit the greedy choice property, which means that making the locally optimal choice at each step will always lead to the globally optimal solution. Many problems do not exhibit this property.

Difficulty of Proof: It can be challenging to prove that the Greedy Algorithm will always lead to the optimal solution. In some cases, it may require sophisticated mathematical proofs to show that the algorithm is correct.

Greedy Algorithm should be used when the problem has the following properties:

The problem can be broken down into smaller subproblems that can be solved independently.

The optimal solution to the problem contains subproblems that also have optimal solutions.

The optimal solution to the problem can be obtained by making locally optimal (i.e., greedy) choices.

If the problem satisfies these properties, then a Greedy Algorithm can provide a fast and simple solution that finds a near-optimal solution. Generally, Greedy Algorithms are best used when the problem has a set of constraints that make locally optimal choices guarantee global optimality, and when a fast and simple solution is preferred over a more complex algorithm that may have better theoretical guarantees but is slower in practice.

Now, let's apply the Greedy Algorithm to solve a real-world problem called the Boats to Save People Problem.

The problem goes like this: You are given an array of people's weights and a boat that can carry a maximum weight of `n`

pounds. You need to determine the minimum number of boats required to save all the people. Each boat can carry a maximum of two people at a time, provided the sum of their weights is at most `n`

pounds.

To solve this problem using the Greedy Algorithm, we need to follow these steps:

Sort the array of people's weights in descending/ascend order.

Initialize two pointers, one at the beginning and one at the end of the array.

While the pointers do not cross each other: a. If the sum of the weights of the two people pointed by the pointers is less than or equal to

`n`

, increment the pointer at the beginning and decrement the pointer at the end. b. Otherwise, only decrement the pointer at the end.Increment the boat count for each pair of people.

Let's look at an example to understand this better:

Suppose we have the following array of people's weights: [150, 80, 100, 110] and a weight limit of 300 lbs. We need to determine the minimum number of boats required to save all the people.

Using the Greedy Algorithm, we first sort the array in descending order: [150, 110, 100, 80].

Next, we initialize two pointers, one at the beginning and one at the end of the array:

csharp

1[150, 110, 100, 80]2^ ^3beginning ending

Since the sum of the weights of the two people pointed by the pointers is greater than 300, we decrement the pointer at the end:

csharp

1[150, 110, 100, 80]2^ ^3beginning ending

The sum of the weights of the two people pointed by the pointers is less than or equal to 300, so we increment the pointer at the beginning and decrement the pointer at the end:

csharp

1[150, 110, 100, 80]2^ ^3beginning ending

Since the sum of the weights of the two people pointed by the pointers is less than or equal to 300, we increment the pointer at the beginning and decrement the pointer at the end:

csharp

1[150, 110, 100, 80]2^ ^3ending beginning

Now, the pointers have crossed each other, and we have saved all the people using two boats.

Now, let's compare the time complexity of using a for loop versus using the Greedy Algorithm to solve the Boats to Save People Problem.

If we were to solve this problem using a for loop, we would iterate through the array of people's weights, selecting pairs of people whose sum is less than or equal to 300. This approach has a time complexity of O(n^2), where n is the number of people. Below is a code example using a for loop:

1function numBoatsForLoop(people) {2people.sort((a, b) => b - a);3let numBoats = 0;4let used = new Array(people.length).fill(false);5for (let i = 0; i < people.length; i++) {6if (!used[i]) {7used[i] = true;8let weightLeft = 300 - people[i];9for (let j = i + 1; j < people.length; j++) {10if (!used[j] && people[j] <= weightLeft) {11used[j] = true;12weightLeft -= people[j];13break;14}15}16numBoats++;17}18}19return numBoats;20}

On the other hand, the Greedy Algorithm has a time complexity of O(n log n), where n is the number of people. The time complexity is dominated by the sorting step, which takes O(n log n) time. Once the array is sorted, we only need to iterate through it once, making the algorithm much faster than using a for loop. Below is a code example using the Greedy algorithm:

1function numBoatsGreedy(people) {2// sort the array of weights from lightest to heaviest3people.sort((a, b) => b - a);4let numBoats = 0;5let minPointer = 0, maxPointer = people.length - 1;6while (minPointer <= maxPointer) {7if (people[minPointer] + people[maxPointer] <= 300) {8i++;9}10j--;11numBoats++;12}13return numBoats;

Activity Selection Problem

Fractional Knapsack Problem

Huffman Coding Problem

Coin Change Problem

Interval Scheduling Problem

The Greedy Algorithm is a simple yet powerful algorithmic technique used to solve optimization problems. It works by making the locally optimal choice at each step, without worrying about the future consequences. We applied this algorithm to solve the Boats to Save People Problem and compared its time complexity to using a for loop. The Greedy Algorithm was much faster, making it a more efficient way of solving this problem.

Tags:

algorithms

Written by Alissa Nguyen

FollowAlissa Nguyen is a software engineer with main focus is on building better software with latest technologies and frameworks such as Remix, React, and TailwindCSS. She is currently working on some side projects, exploring her hobbies, and living with her two kitties.

Learn more about me

Built and designed by Alissa Nguyen a.k.a Tam Nguyen.

Copyright © 2024 All Rights Reserved.