Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items
If $W \ge n \cdot P$ you can add all elements in the knapsack.
Otherwise $W &lt; n \cdot P$ in which case any algorithm with complexity $O(n W)$ will also have complexity $O(n \cdot (nP)) = O(n^2P)$. In particular the pseudo-polynomial dynamic programming solution described in Wikipedia works in $O(n W)$.