We are going to prove that the Knapsack-search is NP-complete. We will do this using the 3-SAT but first going through the Subset-sum problem.

Subset-sum problem

Statement

This can be solves using Dynamic Programming in a similar way to the Knapsack problem in $O(nt)$. However, similar to the Knapsack problem this is not a polynomial time algorithm in the length of the input as that is $n\log_2(t)$. Therefore it is Pseudo-polynomial.

Subset-sum problem is in NP

Moreover it is NP-complete.

Subset-sum problem is NP-complete

Knapsack problem

This subset-sum problem is very similar to the Knapsack-search problem so we have the following.

Knapsack-search is NP-complete