Research On Optimization Of Dynamic Programming Algorithm In Time Efficiency

In the 1950 s, American mathematician R.E.Bellman puts forward the famous optimization, the optimized principle which had laid a solid foundation for Dynamic Programming, the basic thought of dynamic programming to solve the optimization problem is to decompose the problem into some sub problems,So the original problem can transform into some sub problems, first solve the sub problems, and then solve the original problem by combining sub problem solutions. Dynamic programming is a powerful tool to solve the problem of multistage decision.Dynamic programming is an important thinking in program design. In the past 50 years,Dynamic programming has been widely used in various fields to solve problems of various types.Such as the shortest path problem, project group of resource optimization, capital investment decisions, string matching, equipment update, map navigation, scheduling of water resources allocation problem and so on.most of the case, the dynamic.programming can solve the dynamic decision problems efficiently.So the study of the dynamic programming algorithm both in theory and in practice has important meaning.This article mainly state the basis theoretical of dynamic planning, time efficiency optimization to improve the aspects of content.Specific as below.Terminology used in dynamic programming are introduced, such as phase, status, multistage decision-making, index function, the state of the nature of optimal substructure and no aftereffect, overlapping substructure, such as some proper nouns,and summarizes the common child problems in dynamic programming mode,acrossing the basic theory of dynamic programming algorithm.Compared with common algorithm, dynamic programming is discussed by comparison with other algorithms to get to know the dynamic programming of high space consumption, global optimization and high efficiency, etc.To explore the optimization of dynamic programming in time efficiency. Existing research general design the optimization measures for the characteristics of the specific,when the problem is different, the corresponding optimization measures will not work. Due to the dynamic programming method tend to exist a certain amount of time redundancy after the simple design. This paper analyzed the time complexity of the dynamic programming method, will affect its time efficiency from three aspects:need to compute the number of the state in the Problems, the number of involved in the transfer of state, optimization of the state transition time. So on the whole, it can solve the problem of larger data size by promoting the algorithm's time efficiency.In order to verify the effectiveness of the dynamic programming algorithm of time efficiency optimization measures, apply dynamic programming in knapsack problem, a classic optimization problem.First, this paper researches a kind of conventional to solve 0/1 knapsack problem and the multiple knapsack problem of the dynamic programming algorithm,Then using dynamic programming optimization measures to improve the original dynamic programming algorithm.In dealing with the same scale and different algorithm through the experiment data set time efficiency.