# Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the problem using dynamic programming in $$O(n^2P)$$. Anyone have an idea how to solve it?

• There is a common dynamic programming solution for knapsack which works in $O(nP)$. See in Wikipedia – Marcelo Fornet Jun 22 '20 at 17:40
• I know about solution in $O(nW)$, I need in $O(n^2P)$ – user2207686 Jun 22 '20 at 17:45

If $$W \ge n \cdot P$$ you can add all elements in the knapsack.
Otherwise $$W < 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)$$.