International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 9, No. 5, 8 May 2017
Cover page and Table of Contents: PDF (size: 556KB)
Author(s)
Index Terms
Knapsack, memory, maximization, dynamic programming, algorithm
Abstract
Knapsack problem model is a general resource distribution model in which a solitary resource is allocated to various choices with the aim of amplifying the aggregate return. Knapsack problem has been broadly concentrated on in software engineering for a considerable length of time. There exist a few variations of the problem. The study was about how to select contending data/processes to be stacked to memory to enhance maximization of memory utilization and efficiency. The occurrence is demonstrated as 0 – 1 single knapsack problem. In this paper a Dynamic Programming (DP) algorithm is proposed for the 0/1 one dimensional knapsack problem. Problem-specific knowledge is integrated in the algorithm description and assessment of parameters, with a specific end goal to investigate the execution of finite-time implementation of Dynamic Programming.
Cite This Paper
Dominic Asamoah, Evans Baidoo, Stephen Opoku Oppong, "Optimizing Memory using Knapsack Algorithm", International Journal of Modern Education and Computer Science(IJMECS), Vol.9, No.5, pp.34-42, 2017. DOI:10.5815/ijmecs.2017.05.05
Reference
[1]Gil-Lafuente, A., de-Paula, L., Merig-Lindahl, J., M., Silva-Marins, F., and de Azevedo-Ritto, A. (2013). Decision Making Systems in Business Administration: Proceedings of the MS'12 International Conference. World Scientific Publishing Co., Inc. Retrieved from http://dl.acm.org/citation.cfm?id=2509785
[2]Silberschatz, A., and Peterson, J. (1989). Operating System Concepts. Addison-Wesley, Reading.
[3]Chen G., Chern M., and Jang J. Pipeline architectures for dynamic programming algorithms. Parallel Computing, 1(13):111 – 117, 1990.
[4]Coquand,T., Dybjer, P., Nordström, B., and Smith, J. (1999). Types for Proofs and Programs, International Workshop TYPES'99, Lökeberg, Sweden, Available from: Selected Papers. Lecture Notes in Computer Science 1956, Springer 2000, ISBN 3-540-41517-3.
[5]Pisinger, D. (1994). Core problems in knapsack algorithms. Operations Research 47, 570-575.
[6]Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer, Berlin Heidelberg.
[7]Cáceres E. N., and Nishibe, C. (2005). 0-1 Knapsack Problem: BSP/CGM Algorithm and Implementation. IASTED PDCS: 331-335.
[8]Robert M, & Thompson, K (1978). Password Security: A Case History. Bell Laboratories, K8.
[9]Chu P.C and Beasley J. E. (1998), A genetic algorithm for multidimensional knapsack problem. Journal Heuristics. 4:63-68.
[10]Oppong, O. E. (2009). Optimal resource Allocation Using Knapsack Problems: A case Study of Television Advertisements at GTV. Master’s degree paper, KNUST.
[11]Kalai, R. and Vanderpooten, D. (2006). Lexicographic a-Robust Knapsack Problem http://ieeexplore.ieee.org/xpl/freeabs
[12]Benisch, M., Andrews, J., Bangerter, D., Kirchner, T., Tsai, B. and Sadeh, N. (2005). CMieux analysis and instrumentation toolkit for TAC SCM. Technical Report CMU-ISRI-05-127, School of Computer Science, Carnegie Mellon University.
[13]Shang, R., Ma, W. and Zhang, W (2006). Immune Clonal MO Algorithm for 0/1 Knapsack Problems. Lecture Notes in Computer Science, 2006, Volume 4221/2006, 870-878.
[14]Kosuch, S. and Lisser, A. (2009). On two-stage stochastic knapsack problems. Discrete Applied Mathematics Volume 159, Issue 16.
[15]Florios, K. et. al. (2009). Solving multi objective multi constraint knapsack problem using Mathematical programming and evolutionary algorithm. European Journal of Operational Research 105(1): 158-17.
[16]Horowitz, E. and Sahni, S. (1972). Computing partitions with applications to the Knapsack Problem. Journal of ACM, 21, 277-292.
[17]Nauss, R,. M. (1976). An Efficient Algorithm for the 0-1 Knapsack Problem. Management Science, 23, 27-31.
[18]Martello, S., Pisinger, D. and Paolo, T. (2000). New trends in exact algorithms for the 0 – 1 knapsack problem. http: // citeseerx.istpsu/viewdoc/download?doi10.1.11. 89068rep=rep|type=ps
[19]Silva et.al (2008). Core problem in bi criteria 0-1 knapsack problems. Retrieved from: www.sciencedirect.com
[20]Yamada, T, Futakawa, M., and Kataoka, S. (1998). Some exact algorithms for the knapsack sharing problem. www.sciencedirect.com
[21]Lin and Wei (2008). Solving the knapsack problem with imprecise weight coefficients using Genetic algorithm. www.sciencedirect.com
[22]Bortfeldt A, Gehring H. (2001). A hybrid genetic algorithm for the container loading problem [J]. European Journal of Operational Research, 2001, 131(1):143-161.
[23]Simoes, A, and Costa, E. (2001). Using Genetic Algorithm with Asexual Transposition. Proceedings of the genetic and evolutional computation conference (pp 323-330).
[24]Babaioff, M. et al (2007). Matroids, secretary problems, and online mechanisms. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Pages 434-443
[25]Hanafi, S. and Freville, A. (1998), An efficient tabu search approach for the 0-1 multidimensional knapsack problem. http://www.sciencedirect.com