2012•Unpublished venueRequires access

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

Ritika Mahajan, Sarvesh Chopra

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.

About this research paper

What this paper is about

Why it matters

OpenAlex reports 5 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Key concepts: Knapsack problem, Continuous knapsack problem, Change-making problem, Mathematical optimization, Cutting stock problem, Polynomial-time approximation scheme, Generalized assignment problem, Greedy algorithm