Literature review on comparing between different approaches to solve the 0-1 knapsack problem
Abstract & Details
Research Area
Information Technology
Keywords
KNAPSACK
GREEDY ALGORITHM
DYNAMIC ALGORITHM
Abstract
The purpose of this paper is to analyze several algorithm design paradigms applied to a single problem - the 0/1 Knapsack
Problem. The Knapsack problem is a combinatorial optimization problem where one has to maximize the bene fit of objects in a knapsack without exceeding its capacity. It is an NP-complete problem and as such an exact solution for a large input is practically impossible to obtain. The main goal of the paper is to present a comparative study of the brute force, dynamic programming,and greedy algorithms. The paper discusses the complexity of each algorithm in terms of time requirements, and in terms of required programming efforts. Our experimental results show that the most promising approaches are dynamic programming.
License
This work is licensed under a Creative
Commons
Attribution-ShareAlike 4.0 International License.
Author Information
| # | Name | Institute / Affiliation |
|---|---|---|
| 1 | Bhumi K. Joshi | L.D COLLEGE OF ENGINEERING |
How to Cite
Use the following formats to cite this article in your research.
APA Style
Joshi, Bhumi K. (2017). Literature review on comparing between different approaches to solve the 0-1 knapsack problem. International Journal of Advance Research and Innovative Ideas In Education, 3(5), 1360-1364.
MLA Style
Joshi, Bhumi K.. "Literature review on comparing between different approaches to solve the 0-1 knapsack problem." International Journal of Advance Research and Innovative Ideas In Education, vol. 3, no. 5, 2017, pp. 1360-1364.
IEEE Style
Bhumi K. Joshi, "Literature review on comparing between different approaches to solve the 0-1 knapsack problem," International Journal of Advance Research and Innovative Ideas In Education, vol. 3, no. 5, pp. 1360-1364, 2017.
Vancouver Style
Joshi Bhumi K.. Literature review on comparing between different approaches to solve the 0-1 knapsack problem. International Journal of Advance Research and Innovative Ideas In Education. 2017;3(5):1360-1364.
Harvard Style
Joshi, Bhumi K. (2017) 'Literature review on comparing between different approaches to solve the 0-1 knapsack problem', International Journal of Advance Research and Innovative Ideas In Education, 3(5), pp. 1360-1364.
Chicago Style
Joshi, Bhumi K.. "Literature review on comparing between different approaches to solve the 0-1 knapsack problem." International Journal of Advance Research and Innovative Ideas In Education 3, no. 5 (2017): 1360-1364.
Turabian Style
Joshi, Bhumi K.. "Literature review on comparing between different approaches to solve the 0-1 knapsack problem." International Journal of Advance Research and Innovative Ideas In Education 3, no. 5 (2017): 1360-1364.
Related Research
DIGITAL DIVIDE AND EQUITY IN ACCESS TO INTERNET: ITS IMPACT TO LEARNERS’ ACADEMIC ACHIEVEMENT
PDF Unavailable
A PHENOMENOLOGICAL STUDY ON THE CHALLENGES, AND COPING STRATEGIES OF SCHOOL HEADS IN USING TECHNOLOGY
PDF Unavailable
INFLUENCE OF TEACHER PERSONAL COMPETENCE AND SCHOOL LEADERSHIP ON STUDENT ACHIEVEMENT IN MEDIA AND INFORMATION LITERACY
PDF Unavailable
A Comprehensive Review of Blockchain in Automotive Data Tracking
PDF Unavailable
IoT-Based Elderly Emergency Health Monitoring System integrated with a Smart Ambulance mechanism
PDF Unavailable
Decentralized Voting System Using Ethereum Blockchain
PDF Unavailable