Practical Solution Algorithm Of The Knapsack Problem

Knapsack problem had wide applications in a lot of fields. Knapsack problem is belongs among NP-hard problems. Since 50s, It always been a hotfield problem. In contrast, lots of newer methods and techniques have been developed by introducing concepts and thoughts in other fields into combinatorial optimization. The researches about theores and algorithms existed to solve combinatorial optimization problems have been carried out with more attention to newer methods. In this paper, Simulation is presented by using MATLAB software. The results shows that these new algorithms are useable. The research fields include:1. Traditional methods and techniques in solving comibinatorial optimization especially knapsack problems is presented. Thus as Branch-and-bound algorithms, Dynamic programming algorithms, Tighter bounds algorithms, Imagecompute, Heuristic algorithm, etc.2. How to use Genetic Algorithm in solving combinatorial optiomization has been studied in detail. A novel genetic algerithm is presented by combining simple GA and dissipative system theory for knapsack problem,and simulation research of solving large scale knapsack prmlem is carried out for this method.The result of this method for solving large scale knapsack problem is greatly improved over simple GA for the result of numerical experiment.3. Ant Colony Optimization is a newer product from simulating behavior of ants in seeking food. It's a kind of bionics random searching algorithm. Usng Ant Colony Optimization to solve combinatorial optimization problems has been studied and the result of recent reserches was given.4. The effect of partical swarm optimization algorithm in combinatorial optimization has been discussed. A new method of connecting 0/1 knapsack problem with partical swarm optimization was devised after analizing the advantage and disadvantage of partical swarm optimization. Analisis and research for the result of the experiment is carried out, and the differences between the various algorithms are given. The direction of study in future is given.