2
$\begingroup$

I want to show that the problem below, also known as the Knapstack Problem, is in NP (non-deterministic polynomial time). Where should I start?

Given $n$ items numbered $1$ through $n$ so that $i^{th}$ item has weight $w_i$ and value $v_i$, determine whether it is possible to select some of these items with total weight at most $W$ and total value at least $V$.

  • 0
    Knapsack is clearly in NP, since we can guess what items to take and then verify in polynomial time if this is a correct solution according to our requirements.2011-10-12

1 Answers 1

1

Loosely speaking, being in NP means it's possible to verify any proposed solution efficiently. If someone proposes a selection of items, all you have to do to verify the proposal is to add up the weights and see you get at most $W$, and add up the values and see you get at least $V$.