The Quadratic Knapsack Problem (QKP) is a combinatorial optimization problem that has attracted much attention over the past four decades. In this problem, one seeks to maximize a quadratic objective function of binary variables subject to a single linear knapsack constraint. This problem is interesting from both the practical and the theoretical points of view. In fact, applications of the QKP can be found in finance, logistics, and telecommunications, among others. It often appears as a subproblem to other combinatorial optimization problems. The QKP is known to be NP-hard in the strong sense. This paper proposes a novel idea that improves the regular value function found in the literature of dynamic programming (DP) for the QKP. We propose to consider an item with its contribution to both the items already selected in a given packing as well as an estimate of its potential contribution with respect to items yet to be considered. We also propose a propagation and a novel local search procedure to further improve the quality of the obtained results. The computational experiments show that our algorithm can dominate the performance of the existing deterministic heuristics in terms of the quality of the solutions for the standard QKP instances. Moreover, our novel algorithm significantly outperforms these heuristics on newer and more challenging QKP instances. It finds optimal or near-optimal solutions to the most challenging class of QKP instances, yielding improvements of up to 99% with respect to solutions that can be found with the existing algorithms.