Dynamic programming

Dynamic Programming, also known as DP algorithm (short for Dynamic Programming), was originally a branch of operations research and is a mathematical method used to solve the optimization of decision processes.

Dynamic programming algorithms are usually used to solve problems with certain optimal properties.

Application scenarios of dynamic planning:

The problems applicable to dynamic programming must satisfy the optimization principle, have no aftereffect and overlap. 1. The principle of optimization (Optimal substructure properties) The principle of optimization can be stated as follows: an optimization strategy has the property that, regardless of past states and decisions, the remaining decisions must constitute an optimal strategy for the state formed by previous decisions. In short, the substrategies of an optimization strategy are always optimal. A problem satisfying the optimization principle is said to have the property of optimal substructure.

2. No aftereffect After all stages are arranged in a certain order, for a given stage state, the state of its previous stages cannot directly affect its future decision, but only through the current state. In other words, each state is a complete summary of past history. This is called no backwardness, also known as no aftereffect.

3. The overlapping dynamic programming of subproblems improves the search algorithm with exponential time complexity to one with polynomial time complexity. The key is to solve the redundancy, which is the fundamental purpose of dynamic programming algorithm. Dynamic programming is essentially a technology that swaps space for time. In the process of implementation, it has to store various states in the process of generation, so the spatial complexity is greater than other algorithms.

Knapsack problem

Given n items and a backpack of capacity C, item I weighs W and has a value of V.

Q: How should items be selected to maximize the total value of items in a backpack?

Specific topics

You can use a table to illustrate

Solution summary: 1. If the current item does not fit, then the best combination of the first N items is the same as the best combination of the first N-1 items. Two, if can hold the current item. Hypothesis 1: The total value is the best combination of the first N-1 items plus the value of the current item, given the space reserved for the current item. Hypothesis 2: Without the current item, then the best combination of the first N items is the same as the best combination of the first n-1 items. Select the larger value in hypothesis 1 and hypothesis 2 as the value of the current best combination.

 

Backtracking of the backpack problem

Question: What are the items in the backpack that maximize the total value of the backpack?

It’s like going backwards in a table

Summary: Starting from the bottom right corner of the table, if the value of the first n best combinations of items is the same as the value of the first n-1 best combinations of items, the NTH item has not been loaded. Otherwise, the NTH item is loaded.

Source of learning

www.bilibili.com/video/av629…

 

 

 

Learn together and make progress together. If there are any mistakes, please comment