Theses / Dissertations >
College of Science >
Please use this identifier to cite or link to this item:
|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|
|Appears in Collections:||College of Science|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.