| Knapsack problem is a classical combinatorial optimization problem. It has been researched by numerous researchers from various perspectives, and various ideas in algorithm design come into being. Because of the property of NP-complete in knapsack problem, how to make balance between time efficiency and precision becomes the main factor in algorithm design of knapsack problem.Recent years, data mining is one of the fastest developing technologies in information field. Because data mining has powerful function to discover useful knowledge, we use it to find similar state space of knapsack problem, and then reduce it.The paper sums up the background of knapsack problem, recent development and future trend, analyzes the property, kinds of mathematical models and strategy of algorithm design. After finished the above basic work, we propose our theoretic innovation, and build the model for solving knapsack problem based on clustering analysis. Then we use the model to solve 0/1 knapsack problem, subset-sum problem and multidimensional knapsack problem. In the experimental part, we evaluate performance of the model, and then we find out that model has good performance and stable approximate factor, and it can find balance between time efficiency and accuracy. The innovative points of our paper states as follows:(1) Based on the mastery of the core technology and idea of data mining, we combine classical knapsack problem and emerging data mining technology, and then propose a model for solving knapsack problem based on clustering analysis.(2) The model has well expansibility, it can use more conformable module according to the different instance. In the course of reduction of knapsack problem, the model can carry out learning unsupervised, get rid of similar state space, and make advantaged condition for expansion of state space.(3) Based on the model, we implement algorithms for 0/1 knapsack problem, subset-sum problem, and multidimensional knapsack problem. |
PDF Full Text Request