Title:
0/1 KNAPSACK PROBLEM: GREEDY VS. DYNAMIC-PROGRAMMING

Authors:
Namer Ali Al Etawi, Fatima Thaher Aburomman, Jordan

Abstract:

Knapsack Problem (KP) is one of the most profound problems in computer science. Its applications are very wide in many other disciplines liken business, project management, decision-making, etc. In this paper we are trying to compare between two approaches for solving the KP, these are the Greedy approach and the Dynamic Programming approach. Each approach is explained by an algorithm. Then results are obtained by implementing the algorithm using Java. The results show that DP outperforms Greedy in terms of the optimized solution, while greedy is better than DP with respect to runtime and space requirements.