Painted levels: being fostered fostered fostered

MrLiuQ: QiShare team

This article introduces the knowledge of dynamic programming.

A list,

Dynamic Programming (DP).

Its core idea is to break a complex problem into several sub-problems and solve the big problem step by step by solving the sub-problems.

Note: The idea of dynamic programming can only be used if and only if each subproblem is discrete (that is, each subproblem is independent of other subproblems).

2. “0-1 Knapsack Problem” of Dynamic Programming

Now there is a situation where “you” are a “thief” and you carry a bag to “steal something”.

Condition 1: Only one item per item, either take it or not. Condition 2: You can carry up to 4kg of stuff. (Fixed size, not full)

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

How can you make the most money by stealing with limited weight?

Scheme 1: Simple algorithm (feasible, not recommended)

Violence enumerates all permutations of goods, discarding all combinations that exceed the weight requirement and picking the largest one.

Yes, but it’s too slow. Every extra item doubles the number of combinations.

Solution evaluation: Time complexity O(2N), super super slow, not recommended.

Scheme 2: Greedy algorithm (not feasible)

Use the greedy algorithm described in the previous article.

An approximate solution is obtained by using a greedy strategy (take the most expensive, take the best value).

Scheme evaluation: this scheme is close to the optimal solution, is approximate solution, but not necessarily the optimal solution, so it is not feasible.

Scheme 3: Dynamic planning (feasible, recommended)
  • Principle: first solve the child backpack optimal, and then solve the large backpack optimal.

So let’s draw a table, and we’ll fill it out column by column. (PS: Experience the algorithm process of dynamic programming)

Table :(actually corresponds to a two-dimensional array)

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A
Commodity B
Goods C
Goods D

So just to read this table,

Row: represents the row of goods (corresponding to I), column: represents the column of weight (corresponding to J), and case: represents the current existing goods and the maximum value that can be taken under the existing weight.

Ok, let’s start by filling in the columns:

In the first row, only good A (value: 3000, weight: 4kg)

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A /
Commodity B
Goods C
Goods D

In the second row, we have commodity A (value: 3000, weight: 4kg) and commodity B (value: 2000, weight: 3kg).

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A /
Commodity B /
Goods C
Goods D

The third row has commodity A (value: 3000, weight: 4kg), commodity B (value: 2000, weight: 3kg) and commodity C (value: 1500, weight: 1kg).

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A /
Commodity B /
Goods C 1500
Goods D

The fourth row has commodity A (value: 3000, weight: 4kg), commodity B (value: 2000, weight: 3kg), commodity C (value: 1500, weight: 1kg), commodity D (value: 2000, weight: 1kg).

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A /
Commodity B /
Goods C 1500
Goods D 2000

Have you noticed that the algorithm for filling out each form here can be expressed as:

If the weight of the item in the corresponding row exceeds the weight of the current child backpack, take the value of the cell in the previous row,

The weight of goods can hold the current child backpack, then take the larger value of the following two:

  • The value of the previous cell (cell[i-1][j])
  • Value of current goods + value of remaining space (Cell [i-1][j- Column number corresponding to the weight of the current item])

Fill in the second column below:

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A / /
Commodity B / /
Goods C 1500 1500
Goods D 2000 3500

The third column:

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A / / /
Commodity B / / 2000
Goods C 1500 1500 2000
Goods D 2000 3500 3500

The fourth column:

Merchandise \ child backpack maximum weight 1kg 2kg 3kg 4kg
Goods A / / / 3000
Commodity B / / 2000 3000
Goods C 1500 1500 2000 3500
Goods D 2000 3500 3500 4000

Judge repeatedly here, so that each cell is the optimal solution, by solving the sub-problem, deduce the final optimal solution. That’s dynamic programming. Isn’t that easy?

Convert to Python code:

def package_dp(a, b, flag, n): c = [[0 for i in range(n)] for j in range(n)] for j in range(n): c[0][j] = 0 for i in range(n): c[i][0] = 0 for j in range(n): if b[i]>flag[j]: c[i][j] = c[i-1][j] else: temp1 = a[i] + c[i-1][j-b[i]] temp2 = c[i-1][j] c[i][j] = max(temp1,temp2) print c[i][j] print ("") return c price = [0,  3000, 2000, 1500, 2000] weight = [0, 4, 3, 1, 1] flag = [0, 1, 2, 3, 4] package_dp(price, weight, flag, 5)Copy the code

Third, details

  • Subbackpack split problem: according to the greatest common divisor of all goods (there may be a decimal) to dismantle the subbackpack.

So that all the goods can be just fit.

  • Through the optimal solution of sub-backpack => deduce the optimal solution of => full backpack.

The idea behind this process is the IDEA of DP.

Application scenarios of dynamic programming

This article cited the backpack and matrix multiplication example, in fact, the idea is the same. The application scenarios are different. Common application scenarios are as follows:

  • 0-1 Backpack problem (✔️)
  • Continuous matrix multiplication (✔️)
  • Coin change
  • String similarity
  • Longest common subsequence
  • Longest increasing subsequence
  • Maximum continuous subsequence sum/product
  • Shortest paths with costs
  • Tile overlay (state compression DP)
  • Workload division

References:

  • Analysis and solution of common dynamic programming problems
  • Matrix multiplication problem for dynamic programming algorithm

Recommended articles:

Dart Foundation (1) Dart Foundation (2) Dart Foundation (3) Dart Foundation (4) iOS SMS Verification code Countdown button iOS environment variables Configure common methods for processing scheduled tasks in iOS