1
$\begingroup$

I'm asking about the question described here: Knapsack Problem with exact required item number constraint

Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check if the constraints are met?

$\endgroup$
1
$\begingroup$

$L$ is given as part of the input, and can be e.g., $n/2$, where $n$ is the number of items. Then, iterating over ${n\choose L}={n\choose \frac{n}2}$ is exponential.

Note that it doesn't matter whether $L$ is given in unary or binary, since $n$ is given in unary (as a list of the different items).

$\endgroup$
2
  • $\begingroup$ But as the author has written - L is given as a constant. $\endgroup$
    – yong
    Jul 18 at 10:21
  • $\begingroup$ The reduction in the answer takes $L$ to be part of the input. If $L$ is an absolute constant, then yes - you can certainly iterate over ${n\choose L}$. $\endgroup$
    – Shaull
    Jul 18 at 10:23

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.