0
$\begingroup$

Is the knapsack problem for a target weight, let's say 1000 for example, and a target price, let's say 10000, still an NPC problem?

$\endgroup$

1 Answer 1

1
$\begingroup$

Probably not. If you have $n$ items, and a capacity of $W$, there is a pseudo-polynomial time algorithm using dynamic programming that runs in $O(Wn)$ time. Thus, for any constant weight, we can solve the Knapsack problem in linear time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.