Painted levels: being fostered fostered fostered

By MrLiuQ Review: QiShare team

This article introduces greedy algorithms.

A list,

Greedy algorithm, also known as “greedy algorithm”. Always do what seems best in the moment when solving a problem. (Local optimal solution) in other words, he does not consider the global optimal solution, what he makes is only a local optimal solution in a sense. Greedy algorithm can not get global optimal solution for all problems, but it can produce global optimal solution or approximate solution of global optimal solution for a wide range of problems. (Source 360 Encyclopedia)

Note: Greedy algorithm is a high-performance algorithm, low complexity, easy to use.

The results of greedy algorithms are not always optimal. For some problems, it can find an optimal solution. In other cases, it can find the ** “approximate solution” of the optimal solution **.

Second, algorithm thought

“Make a big deal out of a big deal.”

  • Minimizing a big problem: divide a complex problem into smaller problems by finding overlaps with sub-problems;

  • Trivial: small problems to find the core of the decision, determine a local optimal solution strategy.

  • By calculating the local optimal solution, we derive the global optimal solution or approximate solution.

The pseudocode is as follows:

Start from an initial solution of the problem while (can move further towards a given overall goal) do selects the current optimal solution as a solution element of the feasible solution; The combination of all the solution elements into a viable solution to the problem.Copy the code

Three, the change problem

This is an example of a greedy algorithm for finding an optimal solution.

Scene: A cashier needs change of 88 yuan. How do you get change? You need the least amount of paper/coins.

¥88 = ¥50 + ¥20 + ¥10 + ¥5 + ¥1 * 3

Each bit of # ARR corresponds to 100, 50, 20, 10, 5 and 1 bills respectively. Arr = [0,0,0,0,0] def change(money): while money >= 1: if money >= 100: if money -= 100 arr[0] += 1 elif money >= 50: money -= 50 arr[1] += 1 elif money >= 20: money -= 20 arr[2] += 1 elif money >= 10: money -= 10 arr[3] += 1 elif money >= 5: money -= 5 arr[4] += 1 elif money >= 1: money -= 1 arr[5] += 1 change(88) print arrCopy the code

Result output:

Four, 0-1 backpack problem

This is an example of a greedy algorithm for approximating the optimal solution. And if you want to find the optimal solution, you have to use DP strategy. Dynamic programming will be introduced in the next chapter.

Scene: a thief went to the shopping mall to steal things, in the backpack weight is limited, how to get more profit? (There is only one item for each item and you can only choose to take it or not)

  • Greedy Strategy 1: Take the most valuable item you can currently hold at a time.
  • Greedy Strategy 2: Pick the current lightest item at a time.
  • Greedy strategy 3: Buy the most cost-effective product every time. (the item with the highest value of price/weight)

Then we analyze them in turn and find counterexamples that are not optimal.

Greedy Strategy 1: Choose the item with the greatest value.

Example: the maximum weight of a backpack is 4kg

goods The price The weight of the
Goods A 3000 yuan 4kg
Commodity B 2000 yuan 3kg
Goods C 1500 yuan 1kg

According to the strategy, first choose commodity A, then can not choose any more, but clearly choose commodity B, C better.

Greedy Strategy 2: Choose the lightest item.

Similar to strategy 1, take a counterexample: the maximum weight of a backpack W = 4kg

goods The price The weight of the
Goods A 3500 yuan 4kg
Commodity B 2000 yuan 3kg
Goods C 1000 yuan 1kg

According to the strategy, choose good C first and then choose good B, but it is clearly better to choose A.

Greedy strategy 3: choose cost-effective goods.

For example:

The maximum weight of the backpack is 4kg

goods The price The weight of the
Goods A 3500 yuan 3.5 kg
Commodity B 3000 yuan 3kg
Goods C 1000 yuan 1kg

At this point, the cost performance is the same. Assuming that commodity A is selected first, it is clear that commodity B and C are better (B and C are 4000 yuan in total, while single option A is only 3500 yuan).

Note: If items can be split into any size, then strategy 3 is optimal. Otherwise, the answer may be approximate.

Therefore, the optimal solution of 0-1 knapsack problem — DP strategy (dynamic programming) will be introduced in the next chapter.

Recommended articles:

Autoresizing iOS Layout Constraint iOS StackView iOS The navigation iOS UIButton will automatically post qiwu weekly according to its content