[proofplan]
We first show that $\mathrm{KNAPSACK}$ belongs to NP by using the chosen subset of items as a certificate and checking the two required inequalities by integer addition. For NP-hardness, we reduce from $\mathrm{SUBSET}\text{-}\mathrm{SUM}$, using each subset-sum number as both the weight and the value of one knapsack item. This forces the knapsack weight and value totals to be the same number, so the simultaneous constraints “at most $t$” and “at least $t$” are equivalent to equality with $t$.
[/proofplan]
[step:Verify membership in NP using the selected item set as certificate]
Let $I = (w_1,\dots,w_n,v_1,\dots,v_n,W,V)$ be an input instance of $\mathrm{KNAPSACK}$. A certificate for a yes-instance is a bit vector $x = (x_1,\dots,x_n) \in \{0,1\}^n$, where $x_i = 1$ means that item $i$ is selected and $x_i = 0$ means that item $i$ is not selected.
Define the total weight function $A_I: \{0,1\}^n \to \mathbb{N}$ by
\begin{align*}
A_I(x) = \sum_{i=1}^n x_i w_i.
\end{align*}
Define the total value function $B_I: \{0,1\}^n \to \mathbb{N}$ by
\begin{align*}
B_I(x) = \sum_{i=1}^n x_i v_i.
\end{align*}
Given $x$, a deterministic verifier computes $A_I(x)$ and $B_I(x)$ by $n$ additions and multiplications by bits, and then checks whether $A_I(x) \leq W$ and $B_I(x) \geq V$. Since all integers are encoded in binary, these arithmetic operations take time polynomial in the input length. Therefore $\mathrm{KNAPSACK} \in \mathrm{NP}$.
[/step]
[step:Reduce subset sum to knapsack by making weight equal value]
We use the known NP-completeness of $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ (citing a result not yet in the wiki: SUBSET-SUM is NP-complete). An instance of $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ is a tuple $(a_1,\dots,a_n,t)$ of positive integers, encoded in binary, and asks whether there exists a subset $S \subset \{1,\dots,n\}$ such that
\begin{align*}
\sum_{i \in S} a_i = t.
\end{align*}
Define a transformation $F$ from $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ instances to $\mathrm{KNAPSACK}$ instances by
\begin{align*}
F(a_1,\dots,a_n,t) = (a_1,\dots,a_n,a_1,\dots,a_n,t,t).
\end{align*}
Equivalently, the resulting knapsack instance has item weights $w_i = a_i$, item values $v_i = a_i$, weight bound $W = t$, and value target $V = t$. The transformation copies the input integers and writes each $a_i$ twice, so it is computable in time polynomial in the binary input length.
[guided]
The reduction is designed to turn an equality constraint into two knapsack inequalities. In $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ we want the selected numbers to add exactly to $t$. In $\mathrm{KNAPSACK}$ we have one upper bound on total weight and one lower bound on total value. To make these two inequalities enforce equality, we give every item the same number as its weight and its value.
Formally, take an arbitrary $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ instance $(a_1,\dots,a_n,t)$, where $a_1,\dots,a_n,t \in \mathbb{N}$. Define the corresponding $\mathrm{KNAPSACK}$ instance by setting
\begin{align*}
w_i = a_i
\end{align*}
for every $i \in \{1,\dots,n\}$, setting
\begin{align*}
v_i = a_i
\end{align*}
for every $i \in \{1,\dots,n\}$, and setting
\begin{align*}
W = t
\end{align*}
and
\begin{align*}
V = t.
\end{align*}
Thus the transformation $F$ is the map from instances of $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ to instances of $\mathrm{KNAPSACK}$ given by
\begin{align*}
F(a_1,\dots,a_n,t) = (a_1,\dots,a_n,a_1,\dots,a_n,t,t).
\end{align*}
This is a polynomial-time transformation because it performs no arithmetic growth: it only copies each integer $a_i$ into two positions and copies $t$ into two positions. Hence the output length is bounded by a constant multiple of the input length, and the construction is computable in polynomial time.
[/guided]
[/step]
[step:Prove that a subset-sum solution gives a feasible knapsack solution]
Assume that $(a_1,\dots,a_n,t)$ is a yes-instance of $\mathrm{SUBSET}\text{-}\mathrm{SUM}$. Then there exists a subset $S \subset \{1,\dots,n\}$ such that
\begin{align*}
\sum_{i \in S} a_i = t.
\end{align*}
For the knapsack instance $F(a_1,\dots,a_n,t)$, the selected subset $S$ has total weight
\begin{align*}
\sum_{i \in S} w_i = \sum_{i \in S} a_i = t = W.
\end{align*}
The same selected subset has total value
\begin{align*}
\sum_{i \in S} v_i = \sum_{i \in S} a_i = t = V.
\end{align*}
Therefore $\sum_{i \in S} w_i \leq W$ and $\sum_{i \in S} v_i \geq V$, so $F(a_1,\dots,a_n,t)$ is a yes-instance of $\mathrm{KNAPSACK}$.
[/step]
[step:Prove that a feasible knapsack solution gives a subset-sum solution]
Assume that $F(a_1,\dots,a_n,t)$ is a yes-instance of $\mathrm{KNAPSACK}$. Then there exists a subset $S \subset \{1,\dots,n\}$ such that
\begin{align*}
\sum_{i \in S} w_i \leq W
\end{align*}
and
\begin{align*}
\sum_{i \in S} v_i \geq V.
\end{align*}
By construction, $w_i = v_i = a_i$ for every $i \in \{1,\dots,n\}$ and $W = V = t$. Hence the two inequalities become
\begin{align*}
\sum_{i \in S} a_i \leq t
\end{align*}
and
\begin{align*}
\sum_{i \in S} a_i \geq t.
\end{align*}
Together these imply
\begin{align*}
\sum_{i \in S} a_i = t.
\end{align*}
Thus $(a_1,\dots,a_n,t)$ is a yes-instance of $\mathrm{SUBSET}\text{-}\mathrm{SUM}$.
[/step]
[step:Conclude NP-completeness from the polynomial reduction]
The preceding two steps prove that, for every $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ instance $(a_1,\dots,a_n,t)$,
\begin{align*}
(a_1,\dots,a_n,t) \in \mathrm{SUBSET}\text{-}\mathrm{SUM} \iff F(a_1,\dots,a_n,t) \in \mathrm{KNAPSACK}.
\end{align*}
Since $F$ is computable in polynomial time, this is a polynomial-time many-one reduction from $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ to $\mathrm{KNAPSACK}$. Because $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ is NP-complete and $\mathrm{KNAPSACK} \in \mathrm{NP}$, $\mathrm{KNAPSACK}$ is NP-complete.
[/step]
