The Quadratic Knapsack Problem (QKP) is a well-known combinatorial optimization problem which amounts to maximizing a quadratic function of binary variables, subject to a single linear constraint. It has many applications in finance, logistics, telecommunications, facility location, etc. The QKP is NP-hard in the strong sense and the state-of-the-art algorithm for solving the QKP can only handle problems of small and moderate sizes. In this paper, we present a novel heuristic algorithm for finding good QKP feasible solutions. This algorithm consists of combining the dynamic programming approach with a local search procedure, with the novelty that both are adapted and implemented in the space of lifted variables of the QKP. The algorithm runs in \({\cal O}(n^3c)\) times and is able to find optimal solutions to more than 97% of standard instances, about 80% of some well-known hard QKP instances, as well as optimality gaps of 0.1% or less for other instances.