A Survey of the Knapsack Problem

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.

• Publication year

  2018

• Venue

  Automation, Control, and Information Technology

• Publication date

  2018-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ACIT.2018.8672677
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computational Aspects of Clearing Continuous Call Double Auctions with Assignment Constraints and Indivisible Demand

  2001cited by this paper
• On quality of service optimization with discrete QoS options

  1999cited by this paper
• Stochastic on-line knapsack problems

  1995cited by this paper
• Knapsack Problems: Algorithms and Computer Implementations

  1990influential reference
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem

  1984cited by this paper
• New Directions in Cryptography

  1976cited by this paper
• The Loading Problem

  1971cited by this paper
• A Branch and Bound Algorithm for the Knapsack Problem

  1967cited by this paper
• The Theory and Computation of Knapsack Functions

  1966cited by this paper
• On the Theory of Dynamic Programming.

  1952cited by this paper
• On the Partition of Numbers

  1896cited by this paper

• TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Design

  2026cites this paper
• Transparency of combinatorial optimisations via machine learning and explainable AI

  2025cites this paper
• BALANCE: Bitrate-Adaptive Limit-Aware Netcast Content Enhancement Utilizing QUBO and Quantum Annealing

  2025cites this paper
• Machine-learning-based hyper-heuristics for solving the Knapsack Problem

  2025cites this paper
• GPU Accelerated Compact-Table Propagation

  2025cites this paper
• Personalized Vacation Planning: An Efficient Heuristic Approach

  2025cites this paper
• Efficient Quantum Answer Set Programming Solver Using Partial Diffusion and Entanglement

  2025cites this paper
• A systematic review of the literature on recent trends in dynamic combinatorial optimization problems linked to meta-learning in metaheuristics and quantum computing

  2025cites this paper
• A Green Multi-Attribute Client Selection for Over-The-Air Federated Learning: A Grey-Wolf-Optimizer Approach

  2024cites this paper
• A New Method for the Techno-Economic Analysis and the Identification of Expansion Strategies of Neutral-Temperature District Heating and Cooling Systems

  2024influential citation
• An Exploratory Study on Machine-Learning-Based Hyper-heuristics for the Knapsack Problem

  2024cites this paper
• Designing Network Topologies of Multiple Reservoir Echo State Networks: A Genetic Algorithm Based Approach

  2024cites this paper
• Strategi Maximum Profit Algoritma Greedy dalam Kecerdasan Buatan Penentu Aktivitas Fisik pada Mobile Exergame

  2023cites this paper
• A Multistep Iterative Ranking Learning Method for Optimal Project Portfolio Planning of Smart Grid

  2023cites this paper
• Multi-User Goal-Oriented Communications With Energy-Efficient Edge Resource Management

  2023cites this paper
• Genetic algorithm introducing the estimation of optimal objective function values in subproblems by pre-training

  2023cites this paper
• Translating Constraints into QUBOs for the Quadratic Knapsack Problem

  2023cites this paper
• Efficient Deep Ensemble Inference via Query Difficulty-dependent Task Scheduling

  2023cites this paper
• Star Partitioning – Improving Multilevel Graph Partitioning using Peripheral Nodes

  2023cites this paper
• Semi-Supervised Classification with A*: A Case Study on Electronic Invoicing

  2023cites this paper
• Analyzing The Most Effective Algorithm For Knapsack Problems

  2023cites this paper
• SVM-Based Task Admission Control and Computation Offloading Using Lyapunov Optimization in Heterogeneous MEC Network

  2022cites this paper
• Dynamic Resource Allocation for Multi-User Goal-oriented Communications at the Wireless Edge

  2022cites this paper
• Multi-Persona Mobility: Joint Cost-Effective and Resource-Aware Mobile-Edge Computation Offloading

  2021cites this paper
• Search Graph Magnification in Rapid Mixing of Markov Chains Associated with the Local Search-Based Metaheuristics

  2021cites this paper
• A Systematic Review of Hyper-Heuristics on Combinatorial Optimization Problems

  2020cites this paper
• Allocating Reticles in an Automated Stocker for Semiconductor Manufacturing Facility

  2020cites this paper
• ALLOCATING RETICLES IN AN AUTOMATED STOCKER FOR SEMICONDUCTOR MANUFACTURING FACILITY

  2020cites this paper
• Performance Comparison of Population-Based Quantum-Inspired Evolutionary Algorithms

  2019cites this paper
• H3T: Efficient Integration of Memory Optimization and Parallelism for High-Throughput Transformer Training

  year unknowncites this paper
• Robust Recourse for Binary Allocation Problems

  year unknowncites this paper