Find in Library

Benchmark instances for the unbounded knapsack problem are typically generated according to specific criteria within a given constant range <i>R</i>, 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 <i>C</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>R</mi><mn>4</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> and space complexity of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>R</mi><mn>3</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula>. Additionally, the algorithm can also solve the All-capacities unbounded knapsack problem within the complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>R</mi><mn>4</mn></msup><mo>+</mo><mi>C</mi><mo>)</mo></mrow></semantics></math></inline-formula>. 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.