Analogy of Greedy Algorithms vs Dynamic programming

  • Abhinav Mani Tripathi, Muskan Agrawal, Vishal Dudgikar, Khushbu Trivedi
Keywords: Greedy Algorithm, Dynamic Programming, 0/1 Knapsack, Algorithm, fractional Knapsack, complexity.

Abstract

This paper discussed the intermediaries between two approaches to problem-solving Algorithm greed and dynamic programming. In this paper we have examined the greedy and dynamic algorithms for the 0/1 Knapsack Problem and the fractional Knapsack Problem. This is a combinatorial challenge for optimization in which the benefit of objects must be maximized while not exceeding capacity. Since it is an NP problem, it is not possible to achieve an exact solution for a large input. As a result, the paper provides a comparison of the Greedy and dynamic methods. It also provides the complexity of each algorithm in terms of time and space requirements. Our experimental results show that in greedy and dynamic programming approaches which is the most promising.

Published
2021-10-27
How to Cite
Vishal Dudgikar, Khushbu Trivedi, A. M. T. M. A. (2021). Analogy of Greedy Algorithms vs Dynamic programming. Design Engineering, 2801-2806. Retrieved from http://www.thedesignengineering.com/index.php/DE/article/view/5758
Section
Articles