<ul>
<li>Knapsack problem is called Weakly NP complete or pseudo-polynomial.
</li>
<li>Time complexity of solving it is - O(n*W) .The value of W is linear but the length of W is exponential - length in terms of bits.
</li>
<li>Pseudo polynomial means - running time is a polynomial in the numeric value of the input, but not in terms of the length of the input.
</li>
<li>This <code>O(n * W)</code> can be rewritten as <code>O(n * 2ʲ)</code>, which exponential in the size of the input.
</li>
</ul>
<img src="https://cdn.hashnode.com/res/hashnode/image/upload/v1718306612563/09257fe7-2c52-41aa-a043-5e97468feb11.png" alt class="image--center mx-auto" />
Refernces:
<a target="_blank" href="https://en.wikipedia.org/wiki/Pseudo-polynomial_time">https://en.wikipedia.org/wiki/Pseudo-polynomial_time</a>
<a target="_blank" href="https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete">https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete</a>
<a target="_blank" href="http://www.derf.net/knapsack/#KnapNP">http://www.derf.net/knapsack/#KnapNP</a>
I think it is more to do with computational Complexity theory than to do with real life problem solving.

* Knapsack problem is called Weakly NP complete or pseudo-polynomial.
    
* Time complexity of solving it is - O(n\*W) .The value of W is linear but the length of W is exponential - length in terms of bits.
    
* Pseudo polynomial means - running time is a polynomial in the numeric value of the input, but not in terms of the length of the input.
    
* This `O(n * W)` can be rewritten as `O(n * 2ʲ)`, which exponential in the size of the input.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1718306612563/09257fe7-2c52-41aa-a043-5e97468feb11.png align="center")

Refernces:

[https://en.wikipedia.org/wiki/Pseudo-polynomial\_time](https://en.wikipedia.org/wiki/Pseudo-polynomial_time)

[https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete](https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete)

[http://www.derf.net/knapsack/#KnapNP](http://www.derf.net/knapsack/#KnapNP)

I think it is more to do with computational Complexity theory than to do with real life problem solving.

0/1 Knapsack - How is it NP Complete?