New answers tagged

2

Whether $n$ is "included in the input" or not is irrelevant. No "tricks" 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 ...


1

Suppose that there are $n$ integer weights of magnitude at most $W$. We can encode each weight in $O(\log W)$ bits, and so the total input length (in bits) is $O(n\log W)$. An algorithm is polynomial if its running time is $O((n\log W)^C)$ for some $C$. Dynamic programming runs in $\Theta(nW)$. Unfortunately, $nW$ cannot be bounded by $O((n\log W)^C)$ for ...


Top 50 recent answers are included