关键词: 蚁群算法 NP-完全问题 整数规划 背包问题

Abstract:

The 0/1 Knapsack Problem is of a class of typical combinatorial optimization problems and is NP-complete. It has important meanings to study it. Aimin g at the characteristics of the multidimensional 0/1 knapsack problem, a binary coding directed graph is designed, which makes the ant colony algorithm suitable for the Knapsack Problem. The simulation results show that the Ant Colony Algorithm is very excellent in solving the multidimensional 0/1 knapsack problem.

Key words: （ant colony algorithrn, NP-complete, integer programming, knapsack problem）