Research Article | OPEN ACCESS
Volume Constraint Model and Algorithm for the 0-1 Knapsack Problem
1M.A. Ofosu, 1S.K. Amponsah and 2F. Appau-Yeboah
1Department of Mathematics, Kwame Nkrumah University of Science and Technology
2Department of Mathematics and Statistics, Kumasi Polytechnic, Kumasi, Ghana
Research Journal of Applied Sciences, Engineering and Technology 2015 11:922-925
Received: September ‎13, ‎2014 | Accepted: ‎September ‎20, ‎2014 | Published: April 15, 2015
Abstract
Today’s economic environment has highlighted the importance of properly optimizing every organization’s asset including space and facilities portfolio. Reducing space cost by using space more efficiently can release funds for other more important activities according to the National Audit Office (NAO) space management in higher education. Utilization rate is a function of a frequency rate and an occupancy rate. The frequency rate measures the proportion of time that space is used compared to its capacity. In this study, we have proposed a new model formulation and algorithm design for the 0-1 knapsack problem. Our proposed algorithm considers volume or space occupancy of the items as paramount, since no matter how profitable the item is to the camper if the volume or the size is bigger than that of the volume of the knapsack since every knapsack also has a volume, there would be no need to force it into the knapsack. The most interesting thing about the algorithm is that, it eliminates symmetric branching tree and the lazy sorting used by most algorithms in the literature. Computational experiments provided also show that our proposed algorithm can be among the most efficient algorithms available in the literature.
Keywords:
0-1 knapsack problem, algorithm development, knapsack model, volume constraint,
Competing interests
The authors have no competing interests.
Open Access Policy
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Copyright
The authors have no competing interests.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|