TransWikia.com

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

Computer Science Asked by user2207686 on November 28, 2021

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?

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

Answered by Marcelo Fornet on November 28, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP