This paper addresses resource allocation problem with a separable objective function under a single linear constraint, formulated as maximizing \(\sum _{j=1}^{n}R_j(x_j)\) subject to \(\sum _{j=1}^{n}x_j=k\) and \(x_j\in \{0,\dots ,m\}\) . While classical dynamic programming approach solves this problem in \(O(n^2m^2)\) time, we propose a regret-enabled greedy algorithm that achieves \(O(n\log n)\) time when \(m=O(1)\) . The algorithm significantly outperforms traditional dynamic programming for small m. Our algorithm actually solves the problem for all \(k~(0\le k\le nm)\) in the mentioned time.