Font Size: a A A

The Study, Based On The Property On The 0-1 Knapsack Problem Algorithm

Posted on:2006-07-05Degree:MasterType:Thesis
Country:ChinaCandidate:Y F ZhengFull Text:PDF
GTID:2208360182456278Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Knapsack Problem is a typical NP-hard in the Operation Research field. Problems in cargo loading, cutting stock, budget control and financial management may be formulated as Knapsack Problems. The research of an efficient algorithm will be significant both in theroy and practice. Generally speaking, all the algorithms can be classfied into two kinds. One can be called the exact algorithms, such as the dynamic programming and branch-and-bound method. The others are approximate ones, such as the ant algorithm, greedy algorithm and evolutionary algorithm. As the exact algorithms all runs in exponential time, many approximate algorithms has been developed since 1960s1.After the introduction of Knapsack Problem, we focus on the basic points, methods and theroies of attribute theory. Then, the QM of items on the basis of the core has been introduced with the thoughts of greedy theories and core problem theories. After the alternation of the ordinary Gauss convertion degree function, we present an approximate algorithm based on the attribute theory. And then, a software package is presented in Java. The design and implementation of the package embody many features of the Java programming language. And the package can be easily extended with a good API.As a part of the package, we designed the knapsack problem instance generator and the KP optimization tool. After hundreds of tests, we give out the statistics of the solving results of the 4 kinds of KP instances, which show the efficiency of our algorithm. The average solution time of a KP with 100 thound items is only 95.64 miniseconds.
Keywords/Search Tags:knapsack problem, core problem, qualitative mapping, conversion degree function
PDF Full Text Request
Related items