Open Access
ARTICLE
Reinforcement Learning for Solving the Knapsack Problem
Zhenfu Zhang1, Haiyan Yin2, Liudong Zuo3, Pan Lai1,*
1 School of Computer Science, South-Central Minzu University, Wuhan, 430074, China
2 Centre for Frontier AI Research, Agency for Science, Technology and Research (A*STAR), Singapore, 138632, Singapore
3 Computer Science Department, California State University Dominguez Hills, Carson, CA 90747, USA
* Corresponding Author: Pan Lai. Email: 
(This article belongs to the Special Issue: The Next-generation Deep Learning Approaches to Emerging Real-world Applications)
Computers, Materials & Continua https://doi.org/10.32604/cmc.2025.062980
Received 31 December 2024; Accepted 31 March 2025; Published online 22 April 2025
Abstract
The knapsack problem is a classical combinatorial optimization problem widely encountered in areas such as logistics, resource allocation, and portfolio optimization. Traditional methods, including dynamic programming (DP) and greedy algorithms, have been effective in solving small problem instances but often struggle with scalability and efficiency as the problem size increases. DP, for instance, has exponential time complexity and can become computationally prohibitive for large problem instances. On the other hand, greedy algorithms offer faster solutions but may not always yield the optimal results, especially when the problem involves complex constraints or large numbers of items. This paper introduces a novel reinforcement learning (RL) approach to solve the knapsack problem by enhancing the state representation within the learning environment. We propose a representation where item weights and volumes are expressed as ratios relative to the knapsack’s capacity, and item values are normalized to represent their percentage of the total value across all items. This novel state modification leads to a 5% improvement in accuracy compared to the state-of-the-art RL-based algorithms, while significantly reducing execution time. Our RL-based method outperforms DP by over 9000 times in terms of speed, making it highly scalable for larger problem instances. Furthermore, we improve the performance of the RL model by incorporating Noisy layers into the neural network architecture. The addition of Noisy layers enhances the exploration capabilities of the agent, resulting in an additional accuracy boost of 0.2%–0.5%. The results demonstrate that our approach not only outperforms existing RL techniques, such as the Transformer model in terms of accuracy, but also provides a substantial improvement than DP in computational efficiency. This combination of enhanced accuracy and speed presents a promising solution for tackling large-scale optimization problems in real-world applications, where both precision and time are critical factors.
Keywords
Knapsack problem; reinforcement learning; state modification; noisy layers; neural networks; accuracy improvement; efficiency enhancement
Login
Register
Submit a Paper
Propose a Special lssue
Download PDF
Downloads
Citation Tools
