Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items
So, after eventually giving up on developing a different algorithm I looked back at the original solution, i.e. the one you can find e.g. on Wikipedia under 0/1 Knapsack problem. 

The idea is to look closely at which fields of the table the algorithm builds are actually necessary, and which are not.