About the pseudo polynomial complexity of the KnapSack 0/1 problem
Whether $n$ is &quot;included in the input&quot; or not is irrelevant. No &quot;tricks&quot; are being used to sneakily hide $n$ from the input by implicitly including it as the length of a list.
The input is at least $n$ bits long because it must include a list of all the values and weights of items. If we are not given the values and weights of the items as part of the input, then how are we supposed to solve the problem (if we do not know the weight/value of some items)?
Now, since we know that the input has length (in bits) at least $n$, any running time of the form $n, n^2, n^3,...$ is polynomial in the length of the input.
However, the length of a (reasonable representation of the input) is at most $O(n\log W)$ (assuming the values of the items are on the same order of magnitude as their weights). For every item we must give the weight and value, and this can be done with $\log W$ bits per item (by giving the binary representation of the weight/value).
As Yuval noted, $nW$ is not polynomial in $n\log W$.
It does not matter if we consider the input as the lists only or the lists &quot;together with&quot; $n$. If we also include $n$ explicitly, it just makes the input $\log n$ bits longer. But since the input is already at least $n$ bits long, having $\log n$ extra bits makes no difference.