Comparision of Dynamic and Greedy Approach for Knapsack Problem

Abstract

The aim of paper is to analyze few algorithms of the 0/1 Knapsack Problem. This
problem is a combinatorial optimization problem in which one has to maximize the benefit of
objects without exceeding capacity. As it is an NP-complete problem, an exact solution for a
large input is not possible. Hence, paper presents a comparative study of the Greedy and
dynamic methods. It also gives complexity of each algorithm with respect to time and space
requirements. Our experimental results show that the most promising approaches is dynamic
programming.