The cubic knapsack problem (CKP) is a combinatorial optimization problem, which can be seen both as a generalization of the quadratic knapsack problem (QKP) and of the linear Knapsack Problem (KP). This problem consists of maximizing a cubic function of binary decision variables subject to one linear knapsack constraint. It has many applications in biology, project selection, capital budgeting problem, and in logistics. The QKP is known to be strongly NP-hard, which implies that the CKP is also NP-hard in the strong sense. Unlike its linear and quadratic counterparts, the CKP has not received much of attention in the literature. Thus the few exact solution methods known for this problem can only handle problems with up to 60 decision variables. In this paper, we propose a deterministic dynamic programming-based heuristic algorithm for finding a good quality solution for the CKP. The novelty of this algorithm is that it operates in three different space variables and can produce up to three different solutions with different levels of computational efforts. The computational results show that our algorithm can find optimal solutions for nearly 98% of the test instances that could be solved to optimality. It also has the merit of finding, in less than five minutes, feasible solutions that cannot be outperformed by commercial solvers in 5 hours. The algorithm also empirically dominates the other existing heuristic algorithm for CKP.