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

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.