CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A Study of Performance Analysis on Knapsack Problem

Published on August 2016 by Pushpa S. K., Mrunal T. V., C. Suhas
journal_cover_thumbnail

National Conference on “Recent Trends in Information Technology"
Foundation of Computer Science USA
NCRTIT2016 - Number 2
August 2016
Authors: Pushpa S. K., Mrunal T. V., C. Suhas
dea9d9f8-1840-4f02-8c0b-6acd87f9d63b

Pushpa S. K., Mrunal T. V., C. Suhas . A Study of Performance Analysis on Knapsack Problem. National Conference on “Recent Trends in Information Technology". NCRTIT2016, 2 (August 2016), 5-10.

@article{
author = { Pushpa S. K., Mrunal T. V., C. Suhas },
title = { A Study of Performance Analysis on Knapsack Problem },
journal = { National Conference on “Recent Trends in Information Technology" },
issue_date = { August 2016 },
volume = { NCRTIT2016 },
number = { 2 },
month = { August },
year = { 2016 },
issn = 0975-8887,
pages = { 5-10 },
numpages = 6,
url = { /proceedings/ncrtit2016/number2/25587-1626/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 National Conference on “Recent Trends in Information Technology"
%A Pushpa S. K.
%A Mrunal T. V.
%A C. Suhas
%T A Study of Performance Analysis on Knapsack Problem
%J National Conference on “Recent Trends in Information Technology"
%@ 0975-8887
%V NCRTIT2016
%N 2
%P 5-10
%D 2016
%I International Journal of Computer Applications
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
  1. Levitin, Anany. The Design and Analysis of Algorithms. New Jersey: Pearson Education Inc. , 2003.
  2. Knapsack problem- Wikipedia, the free encyclopedia. https://en. wikipedia. org/wiki/Knapsack_problem.
  3. Hristakeva, Maya and DiptiSrestha. "Different Approaches to Solve the 0/1 Knapsack Problem", MICS 2005 proceedings. www. micsymposium. org/mics_2005/papers/paper102. pdf.
  4. Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience.
  5. Gossett, Eric. Discreet Mathematics with Proof. New Jersey: Pearson Education Inc. , 2003.
  6. 0/1KNAPSACKPROBLEMhttp://www. swatijain. tripod. com/knapsack2. htm
  7. 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.
  8. Knapsack Problem- Wiki Groups. http://wiki. gametheorylabs. com/groups/kb/wiki/fa460/Knapsack_Problem. html.
  9. Dynamic Programming, 0/1 Knapsack Problem. Dr. Steve Goddard. http://www. cse. unl. edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming. pdf.
  10. S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani. Algorithms.
  11. 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.
  12. The Info List- Knapsack Problem. http://theinfolist. com/php/SummaryGet. php?FindGo=Knapsack%20Problem.
  13. 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/.
  14. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Knapsack Maximize Optimal Solution Efficiency