Call for Paper - September 2020 Edition
IJCA solicits original research papers for the September 2020 Edition. Last date of manuscript submission is August 20, 2020. Read More

A Study of Performance Analysis on Knapsack Problem

Print
PDF
IJCA Proceedings on National Conference on “Recent Trends in Information Technology”
© 2016 by IJCA Journal
NCRTIT 2016 - Number 2
Year of Publication: 2016
Authors:
Pushpa S. K.
Mrunal T. V.
C. Suhas

Pushpa S K., Mrunal T V. and C Suhas. Article: A Study of Performance Analysis on Knapsack Problem. IJCA Proceedings on National Conference on Recent Trends in Information Technology NCRTIT 2016(2):5-10, August 2016. Full text available. BibTeX

@article{key:article,
	author = {Pushpa S. K. and Mrunal T. V. and C. Suhas},
	title = {Article: A Study of Performance Analysis on Knapsack Problem},
	journal = {IJCA Proceedings on National Conference on Recent Trends in Information Technology},
	year = {2016},
	volume = {NCRTIT 2016},
	number = {2},
	pages = {5-10},
	month = {August},
	note = {Full text available}
}

Abstract

The Knapsack problem is a problem in combinatorial optimization, where we find the optimal solution of the given problem such that it satisfies the given constraint. Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman and other knapsack cryptosystems [12]. There are various ways to solve the knapsack problem. In this paper, we present Greedy Algorithm, Dynamic Programming, Branch and Bound Technique to solve the Knapsack problem, along with the analysis of its efficiency, and accuracy. The Greedy, Branch and Bound techniques are modified in pursuance of potency. The Greedy technique is altered to work for a 0/1 Knapsack problem. A recursive method is used for the Branch and Bound technique to expedite the computations and to reduce the memory consumed.

References

  • Levitin, Anany. The Design and Analysis of Algorithms. New Jersey: Pearson Education Inc. , 2003.
  • Knapsack problem- Wikipedia, the free encyclopedia. https://en. wikipedia. org/wiki/Knapsack_problem.
  • Hristakeva, Maya and DiptiSrestha. "Different Approaches to Solve the 0/1 Knapsack Problem", MICS 2005 proceedings. www. micsymposium. org/mics_2005/papers/paper102. pdf.
  • Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience.
  • Gossett, Eric. Discreet Mathematics with Proof. New Jersey: Pearson Education Inc. , 2003.
  • 0/1KNAPSACKPROBLEMhttp://www. swatijain. tripod. com/knapsack2. htm
  • CSCI 5454, CU Boulder. Crowd Source Lecture. DharanijaRamaswamyThatham, Pate Motter. 1 April, 2013. 1. Knapsack Problem. http://tuvalu. santafe. edu/~aaronc/courses/5454/csci5454_spring2013_CSL2.
  • Knapsack Problem- Wiki Groups. http://wiki. gametheorylabs. com/groups/kb/wiki/fa460/Knapsack_Problem. html.
  • Dynamic Programming, 0/1 Knapsack Problem. Dr. Steve Goddard. http://www. cse. unl. edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming. pdf.
  • S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani. Algorithms.
  • David Pisinger. "What are the hard Knapsack Problems?" Computers & Operations Research 32 (2005)www. dcs. gla. ac. uk/~pat/cpM/jchoco/knapsack/papers/hardInstances. pdf.
  • The Info List- Knapsack Problem. http://theinfolist. com/php/SummaryGet. php?FindGo=Knapsack%20Problem.
  • S. P. Sajjan, Ravi kumarRoogi, Vijay kumarBadiger, SharanuAmaragatti. "A New Approach To Solve Knapsack Problem". http://www. computerscijournal. org/vol7no2/a-new-approach-to-solve-knapsack-problem/.
  • Sanjay Rajopadhye, joint work with R. Andonov and V. Poirriez, Université de Valenciennes. "Parallel and VLSI Implementation of the Knapsack Problem". http://www. irisa. fr/cosi/Rajopadhye/knapsack. html.