0
$\begingroup$

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?

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

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

$\endgroup$
2
  • $\begingroup$ I'm not elaborating about the algorithm, since I think the key point of the answer was showing that it works in the expected complexity rather than showing how it works, and it is very known and available elsewhere. $\endgroup$ – Marcelo Fornet Jun 22 '20 at 17:57
  • $\begingroup$ Yes I know the algorithm, I didn't thought going that way of using the same algorithm, interesting point. $\endgroup$ – user2207686 Jun 22 '20 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.