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

Question

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?

Marcelo Fornet · Answer

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)$.

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

One Answer

Add your own answers!

Ask a Question