Abstract: By modifying the data structure of arc consistency algorithm of Knapsacks constraints, we transformed the bitmap to a directed graph, which solved the problem of redundant computation and invalid operation in the arc consistency algorithm of the original knapsack constraint, and accelerated the algorithm to solve the problem of efficiency. Comparative experimental results show that in the face of the same kind of problem, the initialization time of the improved algorithm is increased because the data structure is more complex, but the solution time is improved by 20%—50%. The improved algorithm can reduce the time of solving the problem in the face of the high difficulty of solving the problem.

Key words: constraint satisfaction problem, arc consistency, Knapsacks constraint