Greedy algorithms

In this topic, you will explore one of the main approaches to problem solving: the greedy solving strategy.

The greedy solving strategy makes optimal choices at each step of an algorithm so that optimal local solutions lead to an optimal overall solution.

Greedy algorithms: principles and characteristics

Let's discuss the principles of greedy algorithms.

To begin with, there is an important requirement for the greedy approach: greedy choice property. This property follows the greedy strategy by selecting the best available option at each stage of the algorithm without considering future consequences. The property ensures that a greedy algorithm makes a locally optimal solution, which is expected to lead to a globally optimal solution.

Another noteworthy quality of greedy algorithms is their simplicity. Here, simplicity means straightforward actions that are easy to implement and understand. By selecting the best available option in each case, a greedy algorithm progresses toward a solution without intricate computations or complex data structures.

We may apply greedy algorithms in specific areas where the greedy choice property matters. These areas can be described as problems where optimal choices at each step lead to a globally optimal solution. For instance, minimum-spanning trees, shortest-path algorithms, and so on. Here, the greedy approach makes sense because it simplifies the problem.

On the other hand, we should keep in mind proving the correctness of greedy algorithms: there may be cases where the greedy approach can't guarantee a globally optimal solution, even if it suggests an optimal local solution.

Benefits and limitations

Here are some brief key points on greedy algorithms:

• Intuitive human approach. Greedy algorithms are usually easy to understand as you make straightforward decisions based on local optimization. It can be compared to human intuition, when people make decisions to satisfy a specific criteria and get immediate profit.
• Efficient solutions. Due to locally optimal choices at each step, it can avoid some resource-intensive operations like searching or backtracking.
• Less memory. Compared to other approaches, greedy algorithms have less space complexity. Since they make decisions about a subset of a problem at separate steps, memory requirements can be lower. For example, in a memoization way, the algorithm has to keep some data from previous steps.

However, the greedy approach is not a silver bullet for all cases. Here are its limitations:

• Global optimum. As we know, the greedy approach makes local optimal choices at each step, which should lead to an overall optimal solution. However, it may not always be the case. The algorithm may suggest a suboptimal solution that does not meet the global optimum.
• Backtrack step. After making an optimal decision at the current step, there is no possibility to overwrite this solution for future steps. The algorithm gets "stuck" in the local optimum and can't eventually reach the globally optimum solution.
• Possibility of making a greedy choice. Every local optimal solution must guarantee a globally optimal solution, so problems should meet a specific requirement to be solved by this approach.

Let's look at the typical problems below.

The cash changing problem

In this problem, you need to change some money. You have to provide an optimal way to give change with the fewest number of bills. The number of bills is unlimited. The greedy approach offers a practical and efficient way to solve this problem.

The algorithm follows a simple principle: you select the largest possible denomination of a coin or a bill at each step that is not greater than the remaining amount. By choosing the largest available denomination, the approach tries to minimize the total number of required bills.

We will look through this problem using the case when you need to withdraw money from an ATM. Let's say you have $66 in your account and an ATM uses the U.S. currency system. This system includes bills with the following values: 100, 50, 20, 10, 5, and 1 U.S. dollar.

How would the ATM do that using the greedy approach? Well, in a nutshell, it starts with the largest possible bill and checks if the sum is lower than the bill. If it's lower, it will use the next denomination in descending order, until it reaches the exact required sum of money.

The greedy steps for our case with $66 are the following:

1. Take the largest and check if the sum is lower. In our case, it is 100.
2. Because 66 is lower than 100, we skip it and start with a $50 bill.
3. Check the next denomination in descending order: $20. It doesn't work because the sum of 50 and 20 is more than 66. So, we skip it.
4. Check the next one. In our case, it is 10. Select a $10 bill.
5. After that, take a $5 bill.
6. Finally, take one $1.

This approach results in the fewest number of bills as per the U.S. currency system's design. It is designed with denominations that have a natural divisibility relationship, and it allows the greedy algorithm to produce the optimal solution.

The cash changing problem with a nonoptimal solution

Even so, there could be cases when the greedy approach fails to produce an optimal solution. If the current system lacks a suitable divisibility relationship, the greedy algorithm may not get the minimum number of coins or bills. The following example is not suitable for the greedy approach.

Imagine that you want to withdraw $40 and the ATM includes the denominations of 25, 20, 10, and 5. Using the greedy approach, we will take the following steps:

1. Start with the largest denomination (25).
2. Then, select 10.
3. Finally, select 5.

As a result, we received three bills. However, the optimal solution in this case will be to use two $20 bills. In such cases, it is better to use a dynamic programming approach to achieve an optimal solution.

The knapsack problem

The problem is relatively straightforward: you are given a set of items, each with a specific weight and value. Your task is to find the best way to pack items into a knapsack and maximize the total value of the items. As a limitation, you are given the total weight of the knapsack that can't be exceeded.

A greedy algorithm can also be applied to the knapsack problem, as it allows for quick decision making. For instance, we can select items based on their value-to-weight ratio, which means that we choose items with the highest value and add them to the knapsack step-by-step until the weight constraint is reached.
Let's look at the case in which the greedy approach returns an optimal solution.

You own a container that you can fill with various items and ship the items to your clients. The maximum capacity of the container is 1000 kg. Here are the given items with their weight and value:

Your task is to find a combination of items that provides the maximum total value and won't exceed the capacity of your container.
We're going to use a value-to-weight ratio approach.

Also, we define the weight of the knapsack as W, and the value of items inside as V.
Let's apply the following steps using greedy approach:

1. Select Item 3 and the container has W = 500, V = 1500.
2. Select Item 4 and container has W = 700 (500+200), V = 2100 (1500+600).
3. Try to select Item 2, but it exceeds the maximum weight capacity (700 + 400 > 1000), so skip it.
4. Select Item 1 and container has W = 1000 (700+300), V = 2800 (2100+700).

To sum up, the final optimal solution is items 1, 3, 4, and their total value is 2800.

The knapsack problem with a nonoptimal solution

However, it should be mentioned that the greedy algorithm for the knapsack problem doesn't guarantee an optimal solution for all cases. Because of its focus on immediate local optimization, it doesn't consider the long-term consequences of each decision. Therefore, a greedy algorithm may fail to achieve the globally optimal solution within the given constraints.

We can see that in an example with different values. Imagine you own a container that you can fill with various items and ship the items to your clients. The maximum capacity of the container is 400 kg. Here are the given items with their weight and value:

We use the value-to-weight ratio approach again.

In this example, using the greedy approach, we should select Item 1 with the maximum ratio of 6, but after that, we are not able to add any more items as per the weight limit.

So, the optimal solution would be to sum item 2 and item 3 with the value 1100 + 1000 = 2100 instead of item 1 with the value equal to 1800.

The greedy approach can be used to find the optimal solution to a specific type of knapsack problem: the fractional knapsack problem. This is because the approach considers fractional item values and allows for the inclusion of portions of items based on their value-to-weight ratio.

Here are the steps:

1. Sort the items based on the ratio.
2. Add whole items as long as the capacity allows.
3. If we don't have enough space for the whole item, we can still use fractions of items until the weight limit is reached.

As a result, the greedy approach suits the fractional knapsack problem perfectly. It follows the greedy idea of selecting optimal local solutions and leads to the correct solution even if there is a limitation to selecting the whole item.

When to become greedy

The greedy approach leads to efficient and satisfactory solutions only in some cases.

If you want to check the correctness of your greedy algorithm, you may use trial tests with different inputs. Checking the results of the trial tests provides confidence in the algorithm's correctness, or maybe it can show that some solutions are not optimal.

It is crucial to note that passing the trial tests doesn't guarantee the correctness of your greedy algorithm in all cases. Sometimes it can just lead to verifying the optimal substructure property. As you remember, the optimal solution to a problem can be produced from the optimal solutions to subproblems. However, providing rigorous proof of this property is outside the scope of the topic.

Just keep in mind that, while using a greedy approach, it is important to perform careful analysis and verification. Trial tests can provide some assurance, but they are not a 100% guarantee of correctness.

Conclusion

To sum up, here are the important notes on greedy algorithms:

• They imitate a human approach, where you apply straightforward decisions to achieve optimal local solutions.

• Before using the greedy approach, check the possibility of making the greedy choice.

• Cash problems can be optimally solved if denominations have a natural divisibility relationship.

• The fractional knapsack problem suits the greedy approach perfectly, while the regular knapsack problem may not always produce the optimal solution.

• Always consider the problem's specifics and evaluate if it is sensible to apply a greedy algorithm