An Adaptive Algorithm for the Knapsack Problem

The knapsack problem is a classic NP-hard problem in the combinational optimization. Because it is very hard for the solution,it is very important in the research on cryptosystem and number theory. Based on the famous two-list algorithm and the two-list four-table algorithm,a new adaptive algorithm for the solution of knapsack problem is proposed by adopting the principle of merging and four unbalanced sub-tables. To find the solution for the n -element knapsack problem,the proposed algorithm needs O（ε（2 n/?2 ）） time,1≤ε≤n/4 ,and O（2 n/?2-ε ） memory. The value of parameter ε in the adaptive algorithm can be adjusted in the range from 1 to n/4 accordance with the scale of the knapsack instances and the available computation resource. The theoretic analysis and the computational experiments show that the proposed algorithm can solve the knapsack instances that can’t be solved before in the usual computational environments,thus gaining an improved result over the past researches.