A Survey of the Knapsack Problem | IEEE Conference Publication | IEEE Xplore

A Survey of the Knapsack Problem


Abstract:

The Knapsack Problem (KP) is one of the most studied combinatorial problems. There are many variations of the problem along with many real life applications. KP seeks to ...Show More

Abstract:

The Knapsack Problem (KP) is one of the most studied combinatorial problems. There are many variations of the problem along with many real life applications. KP seeks to select some of the available items with the maximal total weight in a way that does not exceed a given maximum limit L. Knapsack problems have been used to tackle real life problem belonging to a variety of fields including cryptography and applied mathematics. In this paper, we consider the different instances of Knapsack Problem along with its applications and various approaches to solve the problem.
Date of Conference: 28-30 November 2018
Date Added to IEEE Xplore: 25 March 2019
ISBN Information:
Conference Location: Werdanye, Lebanon

I. Introduction

The Knapsack Problem is composed of items, each with its associated weight and profit. The objective is to select a subset of the items that maximizes the profit and that at the same time fits the knapsack. The name of the problem is derived from the situation in which a mountain climber should select a number of items to be included in his knapsack and that he might use during his trip. The difficulty here is that the climber should select items with more profit but in the same time should not exceed the capacity of the knapsack. Scientists have shown interest in this problem because it represents different practical real life situations. In fact, these items could represent n computed data files that need to be stored and we know that there is only W bytes storage available. Therefore the objective is to choose a subset of the files such that the total size does not exceed weight and the stored files' total computing time is maximized. However, the family of Knapsack problems is rich and there are many knapsack variations. In the simple 0–1 Knapsack version, each item can only be picked once. When items should be selected from disjoint sets, then we are encountered with the multiple choice knapsack problems. Another type of knapsack is when there are many knapsacks that can be filled simultaneously.

References

References is not available for this document.