Optimization of the Item Selection Problem Using Multi-Division Dynamic Programming

Dynamic Programming (DP) is a powerful method for solving combinatorial optimization problems. However, it is incapable of finding the optimal solutions of 0-1 integer programming in the multi-dimensional quadratic equation. In this study, we proposed a new approach called ”Multi-Division Dynamic Programming (MDDP)” that improves the efficiency and the accuracy of dynamic programming in constructing parallel tests for minimizing the deviations of quadratic equations. Experimental results show that our proposed approach can construct the parallel tests with the lowest error than the other methods (e.g., Genetic Algorithm, Greedy Approach, Neural Network, Swanson & Stocking, and Wang & Ackerman). The execution-times and the deviation improvement ratios of MDDP are more than 88.3% and 94.9% better than DP. The proposed MDDP would be useful for its effectiveness and accuracy to the item selection problem.