# Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size

arXiv: https://arxiv.org/abs/2005.14105 · HTML: https://mlsanity.com/paper/2005.14105/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2020.

## Built on by (most cited first, 16 of 16)

- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks](https://mlsanity.com/paper/2502.16763/) (2025)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [Unsupervised Extractive Summarization with Learnable Length Control Strategies](https://mlsanity.com/paper/2312.06901/) (2023)
- [All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers](https://mlsanity.com/paper/2410.15601/) (2024)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)
- [Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework](https://mlsanity.com/paper/2312.03413/) (2023)
- [On the expressivity of sparse maxout networks](https://mlsanity.com/paper/2510.14068/) (2025)
- [Tropical Circuits with Scalar Multiplication Gates](https://mlsanity.com/paper/2607.11540/) (2026)

## Abstract (arXiv)

The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard Knapsack Problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a Knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum Knapsack solution is sufficient to find optimum Knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed Knapsack solution: for Knapsack instances consisting of n items, an RNN of depth five and width w computes a solution of value at least 1-O(n2/√w) times the optimum solution value. Our results build upon a classical dynamic programming formulation of the Knapsack Problem as well as a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the Knapsack Problem. A carefully conducted computational study qualitatively supports our theoretical size bounds. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various Shortest Path Problems, the Longest Common Subsequence Problem, and the Traveling Salesperson Problem.