Analysis of 0/1 Knapsack Problem Using Deterministic and Probabilistic Techniques

Author

Mahajan, Ritika ; Chopra, Sarvesh

Author_Institution

M.Tech Comput. Sci. Eng., Shaheed Bhagat Singh Coll. of Eng. & Technol., Ferozepur, India

fYear

2012

fDate

7-8 Jan. 2012

Firstpage

150

Lastpage

155

Abstract

The purpose of this paper is to analyze several algorithm design paradigms applied to single problem - 0/1 Knapsack Problem. The Knapsack Problem is a combinatorial optimization problem where one has to maximize the benefits of objects in a knapsack without exceeding its capacity. It is an NP-complete problem and uses exact and heuristic techniques to get solved. The objective is to analyze that how the various techniques like Dynamic Programming, Greedy Algorithm and Genetic Algorithm affect the performance of Knapsack Problem.

Keywords

computational complexity; deterministic algorithms; dynamic programming; genetic algorithms; greedy algorithms; knapsack problems; 0-1 knapsack problem; NP-complete problem; combinatorial optimization problem; deterministic techniques; dynamic programming; genetic algorithm; greedy algorithm; heuristic techniques; knapsack objects; probabilistic techniques; Algorithm design and analysis; Biological cells; Dynamic programming; Genetic algorithms; Greedy algorithms; Heuristic algorithms; Optimization; Dynamic Programming; Genetic Algorithm; Greedy Algorithm; Knapsack Problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Advanced Computing & Communication Technologies (ACCT), 2012 Second International Conference on

Conference_Location

Rohtak, Haryana

Print_ISBN

978-1-4673-0471-9

Type

conf

DOI

10.1109/ACCT.2012.26

Filename

6168350