Consider the following problem. Given a set of $n$ items having weight $w_i$ and value $v_i$ and a maximum capacity $W$, maximize $\sum\limits_{i=1}^n a _i v_i$ under $\sum\limits_{i=1}^n a_i w_i \leq W$ where $a_i \in \{0,1\}$. That is, choose a subset of items giving the maximum total value while still fitting into the capacity. I am wondering what the time complexity of this problem is and I think that I found that it is not in NP. The reason is that there can be no certificate of correctness for any one particular choice of items. When someone gives me a set I cannot simply check to see that it indeed gives maximum value.
It seems that this problem is at least as hard to check as it is to solve, so it cannot be in NP.
Another line of reasoning leads me to the following: The decision problem can a value of at least $V$ be achieved can be checked in polynomial (actually linear) time by a certificate giving a list of the items. Now a machine can first add up all the values to get $V_{\max}$, and then perform the decision problem for $V = 1, \ldots, V_{\max}$ until the answer is no, having then maximized the sum. This would I guess be an NP computation as we run $V_{\max}$ NP computations and $V_{\max}$ grows linearly with the input.
Hmm, help would be appreciated.
