As a beginner, we have various understandings of dynamic programming and the greedy algorithm. Therefore, many people have some potential misunderstanding of these two ideas. Especially some cannot thoroughly understand the real difference between the two. Don’t worry. We will share AlgoMonster to bring you a clear explanation of greedy and dynamic programming.
Know the Greedy Algorithm
The greedy algorithm, also known as the greedy method, is a standard method to find the optimal solution. This model generally divides the solution process into several steps. Still, each step applies the greedy principle to select the best/optimally choice (the best local choice) in the current state and thus hopes that the final stacked result will also be the best/optimally solution. Looking at the name greed, the inner meaning of the word greed is the most critical. It is like a greedy person who wants to see the best one in front of him in everything, not seeing the long term, and not thinking about the final result and the future, but greedy to maximize the immediate local benefits, a bit of a step-by-step feeling.
The difference between dynamic programming and greedy algorithm
First, in dynamic programming algorithms, the decision made at each step frequently depends on the solution of the relevant subproblem. Therefore the system can make the decision only after it has solved the relevant subproblem. On the other hand, the greedy algorithm only makes the best choice in the current state, i.e., the locally optimal choice, and then translates the corresponding subproblem that results from making this choice. Second, dynamic programming algorithms usually solve each subproblem bottom-up, while greedy algorithms typically proceed top-down.
The basic steps of the greedy algorithm
- Starting from some initial solution.
- Using an iterative process, when it is possible to move one step forward to the goal, a part of the solution is obtained, and the problem is reduced in size according to a locally optimal strategy.
- Combine all solutions.
Two examples to tell the dynamic programming and greedy algorithm
Small change problem
Suppose you have a small store, and you cannot pay electronically, and there are only four kinds of coins in the money cabinet: 25 cents, 10 cents, 5 cents, and 1 cent.
Here are some points that need to be clarified.
We should know ahead that there are only four types of currency: 25, 10, 5, and 1 cent coins.
In this case, finding 41 cents coins for the customer.
Of course, we need to minimize coins.
How will you do it?
We will give the customer 41 cents. The choices are 25 cents, 10 cents, 5 cents, and 1 cents. If you can find 25 cents, do not find the 10 cents first, find the customer 25 cents.
And then the customer still needs 16 (=41-25). The customer receives the change, and the transaction ends.
In our solution, we gave 41 cents at this point, divided into one 25, one 10, one 5, one 1, a total of four coins.
the maximum value in a backpack
There is a backpack that can carry items with a maximum weight of 150. Now there are 7 items (items cannot be divided into arbitrary sizes), numbered 1~7, with weights wi=[35,30,60,50,40,10,25] and values pi=[10,40,30,50,35,40,30] respectively.
Several points need to be clarified here.
The first is that Each item has two attributes: weight and value.
No.2 is that Each selected item and unselected states (there is a problem under discussion).
The last is the list of optional items is known to all, and the total weight of the backpack is certain.
How to have maximum value in the backpack?
Considering the first strategy is value-driven selection, and choose the item with the highest value to put into the backpack each time
We can also use weight-driven selection, select the item with the lightest weight to put into the backpack each time.
And there is also Value density that dominates the selection, choosing the item with the highest value/weight to put in the backpack each time.
- Strategy 1: Value-driven selection, each time choose the highest value items to put into the backpack.
In this strategy, the final choice of items put into the backpack is 4, 2, 6, and 5, and the total weight of the items in the pack is 130, and the total value is 165.
- Strategy 2: Weight-driven selection, each time choose the lightest (small) weight items to put into the backpack
In this strategy, the number of items in the backpack is 6, 7, 2, 1, and 5, and the total weight of things is 140, and the total value is 155.
- Strategy 3: Value density dominates the selection, and the item with the highest value/weight is selected for each section.
The value density of the item “si” is defined as pi/wi, and the value density of these 7 items are si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2].
In this strategy, the final choice is numbered 6, 2, 7, 4, and 1, at which point the total weight of the items is 150, and the real value is 170.
However, let’s review the first example problem.
The problem has changed, and the customer still needs to get 41 cents, and now the currency is only 25 cents, 20 cents, 10 cents, 5 cents, and 1 cent. How?
Follow the three steps of the greedy algorithm.
First, 41 cents, the principle of local optimization, find 25 cents for the customer.
At this point, 41-25 = 16 points. You also need to find the customer 10 points, then 5 points, then 1 point.
Finally, give the customer one 25 cents, one 10 cents, one 5 cents, one 1 cent. It’s in a total of four coins.
Is it not feeling right if you give him two 20 points, plus a 1 point, three coins on it?
Summary of the greedy algorithm
Pros and cons of the greedy algorithm
Pros: It’s simple, efficient, eliminates the need for exhaustive operations required to find the optimal solution, and is often used as an auxiliary algorithm to other algorithms.
Cons: It doesn’t consider other possible situations in general, and each time the locally optimal solution is selected, no more backtracking, so the optimal solution is obtained in very few cases.