A New Algorithm For Knapsack Problem: Reduce Dimension And Recursive Algorithm

Knapsack problem had wide applications in a lot of fields .Knapsack problem is belongs among NP-hard problems. It always had been a hot field problem. In this paper, we analyzed some property for the single restrict integer linear programming(Knapsack problem), Cut the invalided variable and simplify the problem. Designed a new algorithm—reduce dimension and Recursive algorithm. It includes following for chapters.In chapter 1 and 2, author introduces the background of the Knapsack problem and some algorithms. In chapter 3 we give some characters and proof of the problem. In chapter 4, author makes mathematical check for concrete problems, proves the feasibility of new algorithm. And propose the modified method for new algorithm.