Shulou(Shulou.com)11/24 Report--

This article comes from the official account of Wechat: low concurrency programming (ID:dibingfa). The original title: "illustration | you call this stupid thing dynamic planning". Author: flash.

1 Xiao Yu: flash, I have been studying dynamic planning recently, but I just don't understand it. Can you tell me about it?

Flash: no problem. I'm good at this. What's the first thing that comes to mind when it comes to dynamic planning?

Xiao Yu: with regard to the sub-problems and the state transfer equations, they are in a mess. Oh, no, no,

Flash: don't worry, you forget all the nouns and listen to me.

Xiao Yu: OK, go ahead.

Flash: Xiao Yu, let me ask you, how much is it from 1 to 100?

1 + 2 + 3 +. + 100 =?

Xiao Yu: 5050!

Flash: why don't you follow the routine? you should say you don't know.

Xiao Yu: Gauss figured it out a long time ago. I still pretend I don't know. It's too fake.

At the end of the play.

2 flash guest: all right, I'll give you another question.

Xiao Yu: OK, go ahead. I must say I don't know this time.

Flash passenger: there are 10 steps in a staircase. You can only take one or two steps up from the bottom to the top. How many ways are there?

Xiao Yu: well, I really don't know. Let me see.

Xiao Yu: no, I really don't understand. After thinking about the back, I forget the one in front of me.

Flash: you are still stuck in exhaustive thinking. Think carefully about the first question I gave you and see if you have any ideas.

Xiao Yu: Ah! It turns out there's a connection.

Flash: yes, I was going to say that if I told you what one dollar 99 was, would you be able to work out the value of one hundred dollars directly?

Xiao Yu: Oh, I feel a little bit at such a hint! To get to step 10, either go to step 9, then step up step 1, or go to level 8 and then step up step 2 at a time.

Flash: that's great! You found it! Go on.

Xiao Yu: in that case, the number of steps to 10 steps is equal to the number of steps to 9 steps, plus the number of steps to 8 steps.

Flash: good, so if the number of steps to step x is defined as F (x), can you formulate the description just now?

Xiao Yu: that's too easy. The formula is:

F (10) = F (9) + F (8)

Flash: yes, and not only 10 steps, but the number of steps to any step is in line with this logic, so a general formula can be obtained:

F (x) = F (xmur1) + F (xmur2)

Xiao Yu: mm-hmm, to calculate F (10), you only need to know F (9) and F (8), while to calculate F (8), you only need to know F (7) and F (6), and so on.

Flash: that's right. How do you calculate F (2) and F (1)?

Xiao Yu: simple, or is it just logical? if you want to know F (2), you only need to know F (1) and F (0), but what is F (0)? And the calculation of F (1) needs to know F (0) and F (- 1). No, it doesn't make sense.

Flash: , don't worry, in this question, if you only get to the first step, there is only one way to go; if you only get to the second step, there are only two ways to go. It can be obtained directly and intuitively, and there is no need to deduce it.

Xiao Yu: Oh, I see. Since each recursive item in this question needs the support of the first two items, there must be the first two items known, that is, F (1) = 1 and F (2) = 2.

Flash: that's right.

Xiao Yu: mm-hmm, it feels like this will lead to all the results! I'll write the program and take a look.

Flash: don't worry, because this problem is a classic dynamic programming problem, so we use this problem as an example to define the three elements of dynamic programming.

F (xmur1) and F (xmur2) are called the optimal substructures of F (x).

F (x) = F (xmur1) + F (xmur2) is called the state transition equation.

F (1) = 1, F (2) = 2 is the boundary of the problem.

After that, to solve the problem of dynamic planning, as long as you find these three elements.

Xiao Yu: wow, it's sublimated. It's a lot higher in an instant.

Flash: cut the crap, and then see if you can write a program and calculate the result of F (10). This is the difficulty.

Xiao Yu: in programming, it seems to be a recursive problem, simple!

Int getWays (int n) {if (n = 1) {return 1;} if (n = 2) {return 2;} return getWays (NMUE 1) + getWays (NMUI 2);} Flash: well, it's nice, it's simple, but it's too complex, it's O (2 ^ n), you can think about why later. Now you can see if you can reduce the complexity.

Xiao Yu: let me think. When calculating F (10), we need to calculate F (9) and F (8), while when we recursively calculate F (9), we need to calculate F (8) and F (7), so F (8) is repeated here, which is a waste of time.

Flash: yes, in fact, to calculate the value of a new stage, you only need to keep the values of the first two stages all the time, and you can calculate all the way to the final result. For example, define two variables an and b to store the values of the first two stages, when calculating F (3).

Steps

one

234...

Walking method

Axi1

Bread2

three

When calculating F (4), the value of F (1) does not need to be saved, and the new values are replaced by an and b in turn.

Steps

one

234...

ten

Walking method

Axi2

Baked 35

And so on, the value of F (10) is finally calculated.

Steps

one

2...89

ten

Walking method

Axiom 34

Baked 55

Of course, you can keep all the previous values, but this increases the space complexity, depending on your requirements.

Xiao Yu: OK, then the code is easy to write, that's all.

Int getWays2 (int n) if (n = 1) return 1;} if (n = 2) return 2;} int a = 1; int b = 2; int temp = 0; for int i = 3; I = n; iTunes + temp = a + b; a = b; b = temp;} return temp } Flash: yes, this is the correct dynamic programming solution for this problem, and the time complexity is O (N) and the space complexity is O (1).

Xiao Yu: wow, this is dynamic planning. It's so simple.

3 Flash: yes, dynamic planning is not difficult to understand, but the difficulty is that when there are more factors to be considered, that is, changing dimensions, some people will be confused and difficult to find recursive formulas, and this is indeed a difficulty.

Xiao Yu: Oh, really?

Flash: of course. I'll give you another question.

Xiao Yu: come on, brother.

Flash: ahem, then listen carefully.

There is a backpack that can carry items with a weight of 5kg.

There are 4 items, their weight and value are as follows.

So, in the case of not exceeding the load-bearing capacity of the backpack, which items can be put into the backpack to maximize the total value?

Xiao Yu: I see. It's how much money I can carry away with this backpack.

Flash: yes.

Xiao Yu: Oh no, I'm stuck in the traversal thought of walking the stairs again.

Flash: it doesn't matter, this question can come up with traversing ideas, in fact, it is not easy, you can say it first, find a feeling.

Xiao Yu: mm-hmm, that is, every item can be put in a backpack or not.

If the total weight exceeds the backpack load, it doesn't count, or write the value as 0, and then take the one with the greatest value in all cases as a result.

This complexity is also easy to get, that is, O (2 ^ N).

Flash: yes, you have made this very complex algorithm very clear, then you will see if you can solve this problem with the idea of dynamic programming.

Xiao Yu: well, as you said before, the three elements of dynamic programming are the optimal substructure, the state transition equation and the boundary

Flash: yes, there were few variables before, so it was relatively simple. Now that there are more variables, the definition becomes more difficult. Let's start with a few definitions to facilitate description. We express the weight and value of the four items as: W1, w2, w3, w4, v1, and v3, respectively.

If we use

F (WBI)

Express

Use a backpack with a load of W to carry the maximum value of the first item.

That question is actually

Use a backpack with a 5kg load to contain the maximum value of the first four items

In fact, it is a solution.

F (5pr 4)

Can you find the state transfer equation?

Xiao Yu: let me see, if you look at this item alone, there are two possibilities:

The first possibility: if you choose to put it in a backpack, you will already get 6 yuan.

At this time, the remaining load of the backpack is 1kg (5kg-4kg), and the remaining items are the first three items after removing item 4.

Then the maximum value that can be obtained from this part is equivalent to that of

Use a backpack with a 1kg load to hold the maximum value of the first three items

Wow, so this part is

F (1pr 3)

Flash: , you're right when you say it yourself!

Xiao Yu: so finally, if you choose to put item 4 in the backpack, in this case, the maximum value is equal to the sum of the two.

F (1,3) + 6

Flash: great, Xiao Yu, what about the other situation?

Xiao Yu: the second possibility: if you choose not to pack this item 4, it is even easier, it is directly equal to the value of the first three items packed in a back with a load of 5.

F (5,3)

Flash: that's right, and there are only two cases! So can you see if F (5j4) can be represented by the values of these two cases?

Xiao Yu: , it's very simple, which is equal to the maximum value of these two cases.

F (5) 4) = max {F (1, 3) + 6 (5, 3)}

Flash: great. Now that the state transfer equation is out, let's draw a table.

Our goal is to calculate the value in the lower right corner, that is, when the backpack load W = 5, select the maximum value F of the first four items to put into the backpack F (5Jet 4)

Xiao Yu: wow, this form is so clear, according to the above formula

F (5pr 4) = max {F (1pr 3) + 6, F (5pr 3)}

That means all you have to do is know the values of F (1) and F (5), right?

Flash: that's right. Then how do you calculate F (1pd3)?

Xiao Yu: OK, the weight of the backpack is 1 at this time, if you choose to put the third item, eh? It doesn't seem to work. The third item won't fit at all.

Flash: yes, so there is no need to discuss the situation of putting the third item, because it can't be put down at all, so F (1prime3) is directly equal to F (1Magne2), so all you need to know is F (1p2).

In the same way, F (1) is also directly equal to F (1), because the second item cannot be placed when the weight of the backpack is 1.

Flash: Xiao Yu, think about it. What does F (1) equal to?

Xiao Yu: obviously, there is only one item to choose from now, so if you can put it down, of course you can put it down, so the greatest value is the value of the first item 3, that is, F (1) 1 = 3.

Flash: yes, so we have found a boundary value. Xiao Yu, what other boundary values can be obtained directly? You can write it in the form.

Xiao Yu: OK, first of all, the first column shows what happens when the weight of the backpack is zero, which obviously can't hold anything, so it's all zero.

Then the first line is easier to calculate. When the backpack weight > = 1, you can put down the first item, so the maximum value is equal to 3.

Flash: good. Next, fill out all the items in the form in turn, and then you can calculate F (5jue 4).

Xiao Yu: wow, it looks so clear!

Flash: yes, but we just used specific numbers, so let's try to abstract this problem, using a backpack with a W load, carrying N items, and the weight and value of each item are expressed by wi and vi respectively. What is the state transfer equation just now?

Xiao Yu: emm, just now F (5jue 4) = max {F (1je 3) + 6, F (5jue 3)}, if all are expressed as variables, that is

F (WBI N) =

Max {F (W-wn, NMUI 1) + vn,F (W, NMUI 1)}

Flash: good. This is the state transfer equation.

F (W-wn) and F (Wmai N-1) are the optimal substructures of F (Wmai N).

And just now the first row and the first column in the table, that is, F (0J.) And F (., 1) is the boundary value!

Xiao Yu: wow, I love you, flash! Finally, I understand the idea of dynamic planning.

4 Flash: don't be happy too early, although the process looks clear, but the code is still difficult to write, you go back today and try to implement the code.

Xiao Yu: OK, make sure you finish the task.

Flash: it's almost time for dinner. There's a new dumpling restaurant nearby. Would you like to join us?

Xiao Yu: Oh no, if you want to use dinner time to digest the knowledge of dynamic planning at night, don't you still have to implement the code? maybe next time.

Flash: Oh, okay.

In the postscript, by intuitively demonstrating the idea of solving the 01 knapsack problem, this paper briefly illustrates the algorithm core of the dynamic programming idea. Many people may find dynamic planning difficult to understand, so they spend a lot of time understanding its ideas. But in fact, to understand the core ideas, this article is enough, more by constantly doing questions, in turn to help themselves understand the idea of dynamic planning. Therefore, I hope that after reading this article, readers, like Xiao Yu, will start to implement the code and find other variant topics to continue to consolidate.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.