Optimizing Memory using Knapsack Algorithm

Optimizing Memory using Knapsack Algorithm

Автор: Dominic Asamoah, Evans Baidoo, Stephen Opoku Oppong

Журнал: International Journal of Modern Education and Computer Science (IJMECS) @ijmecs

Статья в выпуске: 5 vol.9, 2017 года.

Бесплатный доступ

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.

Еще

Knapsack, memory, maximization, dynamic programming, algorithm

Короткий адрес: https://sciup.org/15014969

IDR: 15014969

Список литературы Optimizing Memory using Knapsack Algorithm

  • 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
  • Silberschatz, A., and Peterson, J. (1989). Operating System Concepts. Addison-Wesley, Reading.
  • Chen G., Chern M., and Jang J. Pipeline architectures for dynamic programming algorithms. Parallel Computing, 1(13):111 – 117, 1990.
  • 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.
  • Pisinger, D. (1994). Core problems in knapsack algorithms. Operations Research 47, 570-575.
  • Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer, Berlin Heidelberg.
  • Cáceres E. N., and Nishibe, C. (2005). 0-1 Knapsack Problem: BSP/CGM Algorithm and Implementation. IASTED PDCS: 331-335.
  • Robert M, & Thompson, K (1978). Password Security: A Case History. Bell Laboratories, K8.
  • Chu P.C and Beasley J. E. (1998), A genetic algorithm for multidimensional knapsack problem. Journal Heuristics. 4:63-68.
  • Oppong, O. E. (2009). Optimal resource Allocation Using Knapsack Problems: A case Study of Television Advertisements at GTV. Master's degree paper, KNUST.
  • Kalai, R. and Vanderpooten, D. (2006). Lexicographic a-Robust Knapsack Problem http://ieeexplore.ieee.org/xpl/freeabs
  • 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.
  • 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.
  • Kosuch, S. and Lisser, A. (2009). On two-stage stochastic knapsack problems. Discrete Applied Mathematics Volume 159, Issue 16.
  • 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.
  • Horowitz, E. and Sahni, S. (1972). Computing partitions with applications to the Knapsack Problem. Journal of ACM, 21, 277-292.
  • Nauss, R,. M. (1976). An Efficient Algorithm for the 0-1 Knapsack Problem. Management Science, 23, 27-31.
  • 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
  • Silva et.al (2008). Core problem in bi criteria 0-1 knapsack problems. Retrieved from: www.sciencedirect.com
  • Yamada, T, Futakawa, M., and Kataoka, S. (1998). Some exact algorithms for the knapsack sharing problem. www.sciencedirect.com
  • Lin and Wei (2008). Solving the knapsack problem with imprecise weight coefficients using Genetic algorithm. www.sciencedirect.com
  • 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.
  • Simoes, A, and Costa, E. (2001). Using Genetic Algorithm with Asexual Transposition. Proceedings of the genetic and evolutional computation conference (pp 323-330).
  • 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
  • Hanafi, S. and Freville, A. (1998), An efficient tabu search approach for the 0-1 multidimensional knapsack problem. http://www.sciencedirect.com
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp