An Improved Unbounded-DP Algorithm for the Unbounded Knapsack Problem with Bounded Coefficients

Yang Yang ()
Additional contact information
Yang Yang: School of Mathematical Sciences, Xiamen University, Xiamen 361005, China

Mathematics, 2024, vol. 12, issue 12, 1-12

Abstract: Benchmark instances for the unbounded knapsack problem are typically generated according to specific criteria within a given constant range R , and these instances can be referred to as the unbounded knapsack problem with bounded coefficients (UKPB). In order to increase the difficulty of solving these instances, the knapsack capacity C is usually set to a very large value. While current efficient algorithms primarily center on the Fast Fourier Transform (FFT) and (min,+)-convolution method, there is a simpler method worth considering. In this paper, based on the basic Unbounded-DP algorithm, we utilize a recent branch and bound (B&B) result and basic theory of linear Diophantine equation, and propose an improved Unbounded-DP algorithm with time complexity of O ( R 4 ) and space complexity of O ( R 3 ) . Additionally, the algorithm can also solve the All-capacities unbounded knapsack problem within the complexity O ( R 4 + C ) . In particular, the proof techniques required by the algorithm are primarily covered in the first-year mathematics curriculum, which is convenient for subsequent researchers to grasp.

Keywords: unbounded knapsack problem with bounded coefficients; dynamic programming; branch and bound; linear Diophantine equation; Frobenius problem; all-capacities unbounded knapsack problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/12/1878/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/12/1878/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:12:p:1878-:d:1416037

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().