In many problems, the dynamic programming algorithm is our best choice. Compared with the recursive algorithm, the time complexity and space complexity of the dynamic programming algorithm are superior, and the data scale that can be processed is larger. However, the time complexity of the dynamic optimization algorithm is O(N*V), that is to say, when the data to be processed is large, there is also the possibility of timeout when using the dynamic programming algorithm. Therefore, we need to Based on optimization.
The optimization methods of dynamic programming include:
1. Use space for time: cache intermediate results in an array to avoid repeated calculations.
2. No aftereffect: Assuming that the problem can be decomposed into several sub-problems, and the solutions of some sub-problems are not affected by the solutions of other sub-problems, some unnecessary calculations can be removed.
3. Pruning: During the search process, use some conditions to limit the range of the optimal solution, filter out parts that do not need to be searched, and improve performance.
4. Dynamic programming and greedy algorithm: When the problem can be solved by greedy algorithm, greedy algorithm should be used first, and its time complexity is lower than that of dynamic programming algorithm.
5. Construct the optimal solution: Using the optimal substructure can reduce the scale of the search, thereby improving the search efficiency.
Sample display
Let’s use a specific example to record the following dynamic optimization process:
Title description:
code snippet:
# Solve the 0-1 knapsack problem
def knapsack(N, V, w, v):
# Initialize the dynamic programming table
dp_table = [[0 for j in range(V + 1)] for i in range(N + 1)]
# use dynamic programming to solve
for i in range(1, N + 1):
for j in range(1, V + 1):
# If the weight of the i-th item is greater than the knapsack capacity j, it will not be loaded into the knapsack
# Since the subscripts of the weight and value arrays start from 0, note that the weight of the i-th item is w[i-1], and the value is v[i-1]
if w[i - 1] > j:
dp_table[i][j] = dp_table[i - 1][j]
else:
dp_table[i][j] = max(dp_table[i - 1][j], dp_table[i - 1][j - w[i - 1]] + v[i - 1])
# return the maximum value
return dp_table[N][V]
if __name__ == '__main__':
#N: Indicates the total category of items in the title
#count: indicates the total number of all items in the title
N, V = map(int, input(). split())
w = []
v = []
count = 0
for i in range(N):
wi, vi, si = map(int, input(). split())
count + = si
# The number of items can be greater than 1, so loop si times to add it to the item
for _ in range(si):
w.append(wi)
v. append(vi)
print(knapsack(count, V, w, v))
This code completes the calculation of the data within the time specified in the title and gets the correct result.
Topic upgrade:
Obviously, compared with the above topic, there is no change in the topic, but the scale of processing data has become larger, and when processing data of this scale, the above code shows a timeout, that is to say, the above dynamic programming algorithm needs to be optimized .
Optimization method:
-
Space complexity optimization
# Solve the 0-1 knapsack problem
def knapsack(N, V, w, v):
# Optimize the original method
#The original method uses a two-dimensional array
#When the number of items and the capacity of the backpack are large, the space complexity and time complexity are O(N*M), which will easily lead to running timeout
#This means that we can optimize this problem from the dynamic programming table
#Declare the meaning array according to the capacity of the backpack
db = [0 for i in range (V + 1)]
#for loop
for i in range(N):
#The inner for loop is a decreasing loop, and will not traverse to w[i]-1
for j in range(V,w[i]-1,-1):
db[j] = max(db[j],db[j-w[i]] + v[i])
return db[V]
if __name__ == '__main__':
#N: Indicates the total category of items in the title
#count: indicates the total number of all items in the title
N, V = map(int, input(). split())
w = []
v = []
count = 0
for i in range(N):
wi, vi, si = map(int, input(). split())
count + = si
# The number of items can be greater than 1, so loop si times to add it to the item
for _ in range(si):
w.append(wi)
v. append(vi)
print(knapsack(count, V, w, v))
The above code converts the state transition table from a two-dimensional array to a one-dimensional array, which reduces the space complexity requirements of the code, but it is not difficult to see that although certain loop conditions are set, the time complexity of the code is still O(N* M), that is, running the question will still time out. The problem is not solved.
Both pieces of code can only pass through 13 sets of data, so they need to be optimized in terms of running time.
-
Time complexity optimization
How to reduce the time complexity, the first thing I think of is paper cutting, through certain conditions, such as dichotomy, to reduce the time complexity to O(NlogM).
# Solve the 0-1 knapsack problem
#Use dichotomy to reduce time complexity
#The first premise is that the weights of the input items should be arranged in an orderly manner, otherwise the dichotomy method for pruning is meaningless
#1. To read the input data, you need to sort the weight of the items, but you must also ensure the correspondence between quality and value, and use a certain data structure to store the best
#2. Sort items by quality
#3. Use dichotomy to reduce time complexity, write Knapsack function
#This method of optimizing time complexity does exist, but in this problem, if you need to use the state of the backpack after each inspection of the item, then this selectivity
#The way to update the state must be wrong, because all possible states after each step of update are not recorded, resulting in the state of the next step being incomplete.
# Get the wrong next transition state, and you will only get a wrong output in the end
def knapsack(N, V, w, v):
#Using single-dimensional array optimization
db = [0 for i in range (V + 1)]
#for loop
for i in range(N):
# Use binary search algorithm to optimize
left, right = 0, V
while left <= right:
mid = (left + right) // 2
if mid < w[i]:
left = mid + 1
else:
right = mid - 1
db[mid] = max(db[mid],db[mid-w[i]] + v[i])
print(db)
return db[V]
if __name__ == '__main__':
#N: Indicates the total category of items in the title
#count: indicates the total number of all items in the title
N, V = map(int, input(). split())
w = []
v = []
count = 0
for i in range(N):
wi, vi, si = map(int, input(). split())
count + = si
# The number of items can be greater than 1, so loop si times to add it to the item
for _ in range(si):
w.append(wi)
v. append(vi)
print(knapsack(count, V, w, v))
The result of running the code:
It can be seen from the running results that this method is wrong.
Mark + recursion code:
def knapsack(N, V, w, v):
#Using the binary optimization method
#Because it is a 0-1 backpack, each item can only be selected once
#So each item can be seen as a binary number
# Declare the variable maxval to store the maximum value
maxval = 0
#declare the variable mask to store the selected items
mask = 0
#for loop
#i is index, mainly used to locate the array
for i in range(N):
#Use the bitwise AND operator & amp;
if (mask & amp; (1 << i)) == 0:
# use the bitwise OR operator |
if V >= w[i]:
maxval = max(maxval, v[i] + knapsack(N, V - w[i], w, v))
mask |= (1 << i)
return maxval
if __name__ == '__main__':
#N: Indicates the total category of items in the title
#count: indicates the total number of all items in the title
N, V = map(int, input(). split())
w = []
v = []
count = 0
for i in range(N):
wi, vi, si = map(int, input(). split())
count + = si
# The number of items can be greater than 1, so loop si times to add it to the item
for _ in range(si):
w.append(wi)
v. append(vi)
print(knapsack(count, V, w, v))
This code looks very similar to ordinary recursion on the surface, but in fact it is very different.
Ordinary recursive method code:
#Read the number of items and the maximum capacity of the backpack
N,V = map(int,input().split())
#Create an array to store the weight and value of items
w=[0]
v=[0]
for i in range(N):
w_i, v_i = map(int, input(). split())
w.append(w_i)
v.append(v_i)
def knapsack(n,cap):
#Set the recursive end condition
if n == 0:
return 0
#When the weight of the item is greater than the capacity of the backpack
if w[n] > cap:
return knapsack(n-1,cap)
return max(knapsack(n-1,cap),knapsack(n-1,cap-w[n]) + v[n])
print(knapsack(N,V))
Analysis of the differences:
Ordinary recursion method: Without the restriction of if conditional statement, the recursive search space is 
. Adding an if statement can reduce some branches, but when the knapsack capacity is large, the restrictive effect of the if statement is limited, and the time complexity is close to O()
Marking + recursion: A binary mechanism is used to mark each item state, put or not put in the backpack. In this case, the recursive search space is reduced to n!. The time complexity is greatly reduced.
In essence, the difference between these two algorithms is the difference between depth-first traversal and breadth-first traversal.
However, the time complexity of marking + recursion is still too high to pass the title.
Binary + Dynamic Programming:
#Read the first line of input, n is the number of input lines (not the total number of items), w is the backpack capacity
n, m = map(int, input(). split())
#v item weight, w means value
v, w = [], []
# Count the number of items
cnt = 0
for i in range(1, n + 1):
# read input data
a, b, s = map(int, input(). split())
k = 1
# Merge the same items into a larger item according to the exponential relationship of 2, mainly used to reduce the number of items
#About my own understanding why it is possible to directly combine multiple small items into one large item into the storage queue
#My doubts at the beginning are assuming such a situation, there is a huge item, after putting it into the backpack, there is still a little space to put some small items
#However, when items are stored in the queue, we directly synthesize small items into large items, in case there is an embarrassing situation, we can put a single small item
#Items, but you can't put in larger items, wouldn't it not reach the optimal value
#Actually, this situation I assume does not exist, because when synthesizing items, the synthesized items are merged from small to large, so when there are n small items
#The order of synthesis must be a, 2a, 4a, 8a..., these small items after synthesis can be combined in various ways to represent any total mass between a~na
while k <= s:
cnt + = 1
v.append(a*k)
w.append(b*k)
s -= k
k *= 2
if s > 0:
cnt + = 1
v. append(a * s)
w. append(b * s)
n = cnt
#One-dimensional array represents the state transition table
f = [0] * (m + 1)
#n After processing, the total number of items in the storage queue
for i in range(1, n + 1):
#m total backpack capacity
for j in range(m, v[i - 1] - 1, -1):
f[j] = max(f[j], f[j - v[i - 1]] + w[i - 1])
print(f[m])
The method passes the test.
Summary: When optimizing the algorithm, time and space complexity need to be considered comprehensively.