The Comparison And Improvement Of Algorithms For Solving The 0-1 Knapsack Problem

As computational complexity is concerned, knapsack problem (KP) is a NP-hard problem. The problem has been a hotspot in algorithm and complexity research field in half a century. In addition, The KP plays an important role in information encryption, project selection, material cutting, cargo packing and internet security etc. So, the study on solution to KP has significance both in theory and practice. The thesis contributes to the following works.(1) Classic algorithms and a hybrid algorithm are designed to solove 0-1 KP.(2) The other hybrid algorithm called RKP algorithm is proposed which improves the space complexity compared with using general dynamic programming to solve 0-1 KP. RKP algorithm combines the dynamic programming and divided and conquered strategy and its time complexity is O(nC), but it reduces the space complexity to O(C). Moreover, RKP algorithm eliminates the backtracking step while meeting the requirement to find the goods put into knapsack.(3) Based on the parallel feature of dynamic programming, we extend the sequential dynamic programming to parallel algorithm. The analysis shows that:The dynamic programming paralleling in row is affected by weight of items, which results in difficulty in accessing data for processors, heavy burden in bandwidth and complicated code; Compared with algorithm paralleling in row, the dynamic programming paralleling in column has greater advantage; When data block size in row processed by every processor is b'=(?) , where C is capacity of knapsack, p is number of processors and n is number of items, the paralleling algorithm has best performance. Then, dynamic programming using dominated technique is extended to parallel algorithm, whose time complexity is O(min{2n/q,nC/q}) under the loading balance condition. (4) Finally, the experimental result shows that different algorithms behave very differently on solving different categories of 0-1 KP. The followings are our conclusions:general dynamic programming and RKP algorithm proposed in this thesis are steady when facing strong correlated, weakly correlated and uncorrelated 0-1 KP; the hybrid algorithm based on two table notation performs not good on solving strong correlated 0-1 KP; to our surprise, brand-and-bound algorithm using Dantzig's upper bound as bound function performs more badly when facing strong correlated problem than backtracking algorithm does; recursive algorithm is only applicative for small scale problem and it performs badly on solving strong correlated problem as well.