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 benefit 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
SecureLite: A Centralized Cybersecurity Management Tool for Small and Medium-Sized Enterprises
Download PDF
AN ONLINE SCHOLARSHIP MANAGEMENT SYSTEM WITH DESCRIPTIVE ANALYTICS FOR TESDA DAVAO DE ORO
Download PDF
DIGITAL DIVIDE AND EQUITY IN ACCESS TO INTERNET: ITS IMPACT TO LEARNERS’ ACADEMIC ACHIEVEMENT
Download PDF
A PHENOMENOLOGICAL STUDY ON THE CHALLENGES, AND COPING STRATEGIES OF SCHOOL HEADS IN USING TECHNOLOGY
Download PDF
INFLUENCE OF TEACHER PERSONAL COMPETENCE AND SCHOOL LEADERSHIP ON STUDENT ACHIEVEMENT IN MEDIA AND INFORMATION LITERACY
Download PDF
Exploring the Intersection between Nigeria’s Cyber policy and National Security: An Examination of International Cooperation, Legal Frameworks and Regulatory Compliance
Download PDF