Key points are not available for this paper at this time.
In this paper, we obtain a number of new simple pseudo-polynomial time algorithms on the well-known knapsack problem, focusing on the running time dependency on the number of items n, the maximum item weight wₘax, and the maximum item profit pₘax. Our results include: - An O (n^3/2 \wₘax, pₘax\) -time randomized algorithm for 0-1 knapsack, improving the previous O (\n wₘax pₘax^{2/3, n pₘax wₘax^2/3\}) Bringmann and Cassis, ESA'23 for the small n case. - An O (n+\wₘax, pₘax\^5/2) -time randomized algorithm for bounded knapsack, improving the previous O (n+\wₘax³, pₘax³\) Polak, Rohwedder and Wegrzyck, ICALP'21.
He et al. (Tue,) studied this question.