KNUSTSpace >
Theses / Dissertations >
College of Science >

Please use this identifier to cite or link to this item: http://hdl.handle.net/123456789/9436

Title: Optimizing memory using knapsack algorithm
Authors: Baidoo, Evans
Issue Date: 27-Oct-2016
Abstract: Knapsack problem model is a general resource allocation model in which a single resource is assigned to a number of alternatives with the aim of maximizing the total return. Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem. The study was about how to select contending data/processes to be loaded to memory to enhance maximization of memory utilization and efficiency. The instance is modeled as 0 – 1 single knapsack problem. In this thesis a Dynamic Programming (DP) algorithm is proposed for the 0/1 one dimensional knapsack problem. Problem-specific knowledge is incorporated in the algorithm description and evaluation of parameters, in order to look into the performance of finite-time implementation of Dynamic Programming. Computer implementation considerations played an important role in its development. We test the presented method with a set of benchmark data and compare the obtained results with other existing heuristics. The proposed method appears to give good results when solving these problems unravelling all instance considered in this study to optimality in "reasonable" computation times. Computational results also shows that the more the number of items or processes, the higher the time to produce optimal results. Conclusively, when the curse of dimensionality can be dismissed, dynamic programming can be a useful procedure for large sequencing problems
Description: A thesis submitted in partial fulfilment of the Requirement for the degree Master of Philosophy (Information Technology), 2015
URI: http://hdl.handle.net/123456789/9436
Appears in Collections:College of Science

Files in This Item:

File Description SizeFormat
EVANS BAIDOO.pdfMain Work1.67 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback