-1
$\begingroup$

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is it true....

I think a found a solution but i'm not sure if it is completely right. The time complexity of the knapsack problem is equal to $O(W \cdot n)$, where $W$ is the capacity of the knapsack, so if we limit it to a polynomial function of $n$ then the complexity will change to $O(P(n) \cdot n)$ which is a polynomial complexity...

$\endgroup$
  • $\begingroup$ So what's the question? It sounds like you have already answered your own question.... You say you can't figure out why it is true, but then you give a reason why it is true. What are your specific doubts or uncertainties about that reason? $\endgroup$ – D.W. Jan 30 '15 at 19:08
1
$\begingroup$

Since knapsack admits pseudo-polynomial time solution running in $O(nW)$, where $W$ is the bag size, if $W=O(n^c)$for some fixed $c$, then the pseudo-polynomial algorithm runs in $O(n^{c+1})$ which is polynomial in $n$.

$\endgroup$

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.