Application of Dynamic Programming Algorithms to Accounting Information Management

Dynamic planning, along with linear planning, nonlinear planning and goal planning, belongs to the same branch of operations research [22], but the obvious difference between dynamic planning and the other three methods lies in the fact that the latter is more applicable to static problems, and dynamic planning is more applicable to the situation where the system contains time variables or variables related to time and its current state is related to both past and future states, and this kind of system can be called a multi-stage decision optimization system. Stage Decision Optimization System, in which the problem to be solved is a multi-stage decision problem.

In solving the multi-stage decision-making problem [23], the optimal solution formulated at a certain moment is not the optimal solution of the whole system process, which needs to be realized in the whole time process by selecting the optimal solution at each time stage to achieve the optimization of the whole system. Of course, dynamic programming is also applicable conditions, that is, the problem to be solved must satisfy the optimization principle and no after-effects. The so-called non-sequitur means that if the state at a certain stage is known, the development of the process after this stage is only related to the state at this stage, and the state experienced before this stage is irrelevant.

Establishing a dynamic planning model is the first step in solving accounting information management problems using kinetic planning algorithms [24], and its general steps are: determining the stage variables. According to the chronological or spatial characteristics, the whole process of all the problems is naturally divided into a number of interconnected phases, so that it is easy to solve the problem in the order of the phases afterwards. Generally, the stage variables are discrete variables, denoted by k = 1,2,3……n.

Determine the state variables and the set of allowed states. The state is the state of nature at the beginning of each stage, and the possible system states at each stage are identified, which are required to characterize the process without posteriority. Typically, the state variable for stage k is denoted by x_k.

Determine the decision variables and the set of allowed decisions. Decisions are choices made after the state of one phase has been determined that have an impact on the state of the next phase. Generally use u_k(x_k) to denote the decision variable when stage k is in state x_k.

Determine the state transfer relationship and write the state transfer equation, i.e., x_k+1 = F(x_k, u_k); determine the value of the indicator for each decision in each state, i.e., V_kn(x_k, u_k, …, x_n+1).

Write the indicator values for dynamic programming based on the principle of optimization.

Using the method of nested backward extrapolation, starting from the last stage, seek the optimization of each sub-process in turn, and finally obtain the optimization of the whole process, form the optimal strategy, and obtain the optimal index value, i.e. f_k(x_k) = optV_kn.

Optimization Principle. A property of this problem is used in practical cases, in transforming the original problem into a subproblem, the original problem is optimal when and only when the subproblem is optimal, this is the optimization principle. The optimization principle is not obvious, nor is it always true. For example, in the management of accounting information in an enterprise, if it is changed to seek the largest gain in single-digit words, the dynamic programming algorithm fails. If the optimization principle holds, the problem is said to have an optimal substructure.

Posteriority-free. Posteriority-free means that the value of each state depends only on the characteristic variable corresponding to the current state, and is independent of the operation used to reach that state. If no posteriority is not satisfied, then the expression of the state transfer equation is unreasonable, because the same state may correspond to many instances of different nature. In the management of accounting information in an enterprise, for a given total number of funds m, the number of operations n, and the corresponding costs C_i and revenues R_i of each operation, once the d value of a state is calculated, it will not be changed, and therefore it can be recorded in an array by using the memorized search method. If the value of d changes due to changes in the values of subsequent nodes, then not only is the memorized search implementation no longer applicable, but the recursive algorithm that solves in the opposite direction is also likely to be wrong.

Overlap of subproblems. In accounting information management, the dynamic programming algorithm improves the original recursive algorithm with exponential complexity into an algorithm with only polynomial time complexity, and the key lies in the reduction of repetitive and redundant operations, which is the fundamental purpose of applying the dynamic programming algorithm. The essence of the dynamic programming algorithm is an algorithmic technique that exchanges the amount of space storage for the speed of time operations. It is realized in the process, had to store the value of each state in the operation process, in order to facilitate the subsequent operation to call the value that has been derived, thus reducing the time complexity. Therefore, problems solved using dynamic programming algorithms generally have one distinguishing feature. Overlap of subproblems. If the subproblems are not overlapping, then this act of storing each state by the dynamic programming algorithm is unnecessary or even a waste of space resources. Although the overlap of sub-problems is not a necessary condition for the applicability of dynamic programming algorithms, but only if the sub-problems have overlap, the application of dynamic programming algorithms compared with other algorithms has the advantage of time-efficiency, and this paper proposes the accounting information management problem to meet the applicability of dynamic programming algorithms, and therefore the optimization of dynamic programming algorithms is designed further in the latter part of the paper.

Before conducting experiments on the application of dynamic programming algorithms to accounting information management, one needs to be familiar with an overview of the complete knapsack problem. An overview of the complete knapsack problem is given next, first given n event, event i has an importance of w_i and a value of v_i and each event has an infinite number of segments. The capacity of the existing knapsack is w_i Find the sum of the maximum values of which events should be done in the knapsack. Where the vector (X₁, X₂, X₃,……, X_n) maximizes the value with the constraints: ∑i=1nViXi . and the sum must satisfy the following constraints: 1∑i=1nViXi≤W,Xi∈{0,1,2,…,W/Wi}

In this case, the complete knapsack problem is similar to the 0/1 knapsack problem, but in the complete knapsack problem, the number of each event is infinite. For each event, there are only two decisions in the 0/1 knapsack problem. Either you choose or you don't choose. However, in the complete knapsack problem, there are not only two strategies associated with the events, but a variety of strategies for choosing 0, choosing 1, and choosing 2 …… W/W_i.

By looking at the idea of the 0/1 knapsack problem, subproblem m(i, j) is defined as the maximum value that can be obtained from the previous i events based on the packet capacity j. Although there are infinitely many of each event, there are still two strategies at a given time, and the corresponding state transition equations are: 2m(i,j)=max{m(i−1,j−x,Wi)+x⋅Vi,0≤x⋅Wi≤j}

The initial iteration condition is: 3m(i,j)=x⋅V1,0≤x⋅W1≤j

This conventional dynamic programming algorithm is often referred to as the NDP algorithm in event-specific applications. Like the 0/1 knapsack problem, the complete knapsack problem requires the computation of subproblems O(nw), but the time to compute each subproblem is no longer a constant, but rather O(w/w). Thus, the NDP algorithm has a time complexity of O(nw(W/W_i)) and a space complexity of O(nw).

For the knapsack problem, the following optimizations can be considered: for two events i, j, if the constraints of W_i ≥ W_j, V_i ≤ V_j are satisfied, the i rd event can be disregarded when loading it into the knapsack. In this way, replacing the i th event loaded into the knapsack with the i th event of low importance and high value can be done in such a way that the total value of the knapsack will not be reduced. This means that this approach can speed up the execution of the algorithm during accounting information management while reducing the overall event types of accounting information management. However, in the special case when any two events i, j are not related on W_i ≥ W_j, V_i ≤ V_j, no event can be removed, and then this method cannot optimize the time efficiency at the time of accounting information management.

Since the complete knapsack is structurally similar to the 0/1 knapsack problem, except that there is only one event in the 0/1 knapsack while there are multiple events in the complete knapsack, the complete knapsack problem can be considered to be converted into the 0/1 knapsack problem. Due to the limitation of the knapsack capacity, the 1st event can only be selected at most [W/W_j ] times in the complete knapsack problem, so we can convert the 1st event to the 0/1 knapsack problem and establish the state transition equation as follows: 4m(i,j)={ max{m(i−1,j),m(i−1,j−Wi)+Vi},j≥Wim(i−1,j),0≤j≥Wi

The initial iteration condition is: 5m(1,j)={ V1,j≥W10,0≤j<Wi

However, the method still has defects in the time efficiency of accounting information management. Here, in order to achieve the purpose of improving the algorithm, this paper proposes a more efficient conversion method. Assuming the inference that for any positive integer n, it can be decomposed into this form of n = 1 + 2 + 4… + 2^k−1 + n – 2^k + 1, where k is the largest integer that satisfies n – 2^k + 1 ≥ 0, and any positive integer c = X₀ × 1 + X₁ × 2 + X₂ × 4 … + X^k−1 + X^k × (n – 2^k + 1)c ∈ {0, 1}, this shows that for any positive integer n can be decomposed into n = 1 + 2 + 4 ⋯ + 2^k−1 + n – 2^k + 1.

The above problem is converted to a 0/1 knapsack problem by inference, the first one is to convert the i st event to a [W/W_i ] event with value V_i and importance W_i. After the algorithm is performed, the conversion process is as follows: the value of each event after the conversion is Xi*Vi and the importance is X_i*W_i, where X_i stands for 1,2,3,4…2^k−1, W/W_i – 2^k + 1, and the i th event is converted to O(log[W/W_i]) can be solved by using the dynamic algorithm of the 0/1 knapsack problem, and the algorithm ‘s time complexity is O(W∑i=1nlog[W/Wi]) . Such a binary algorithm [25] uses the idea of converting a complete knapsack problem into a 0/1 knapsack problem and then solving it, the algorithm is abbreviated as notated as BDP, and its algorithmic path is shown in Fig. 1.

Figure 1.

BDP model path

When performing the computation of subproblem m(i, j), the NDP algorithm refers to states that have already been solved, e.g., X = [j/W_i]. When performing the optimization of the number of states involved in each state transition, the process of solving a problem with a dynamic programming algorithm is essentially the computation of the states defined in the problem. The computational states are usually derived and decisions are made by solving the states; therefore, the number of states involved in the state transitions in the algorithm when computing the states of each subproblem affects the time efficiency of the Dynamic Programming algorithm when applied to the management of accounting information. To solve this problem, it can be considered to optimize the time efficiency of the algorithm by reducing the number of states involved in each state transition, which is derived from the transition equation that points to for each decision in X = 0, 1, 2, …, [j/W_i] when performing the calculation of subproblem m(i, j). By analyzing let X = [j/W_i], the subproblem m(i, j – W_i) that has been solved when computing subproblem m(i, j) is the maximum that can be obtained based on the first i – 1 events of the backpack capacity j – W_i and the i th event of X – 1. The original state transition formula repeatedly refers to a large number of states when computing the subproblem states, so the state transition formula can be optimized as: 6m(i,j)={ max{m(i−1,j),m(i,j−Wi)+Viij≥Wim(i−1,j) 0≤j≥Wi

By analyzing the original state transition formula, it is found that each state transition involves a large number of invalid states. After the analysis of the decision dependencies between the states, the number of states in each state transition is reduced from O(W/W_i) to O(1), while the time complexity has optimized to O(nw). In this process is usually called ODP dynamic programming optimization.

A new dynamic programming algorithm (BDP) is designed by studying the complete backpack problem and the 0/1 backpack problem, which significantly reduces the time complexity by transforming the complete backpack problem into the 0/1 backpack problem, thus improving the operational efficiency of the algorithm. Further, a more efficient Optimal Dynamic Programming (ODP) algorithm is proposed by reducing the number of states involved in each state transition by optimizing the state transition formulation.The ODP algorithm not only reduces the computation of invalid states, but also further improves the time efficiency of the algorithm by reducing the number of state transitions.