The knapsack problem is an $NP$ complete problem and its formulation is similar to the subset sum. Both the knapsack problem and the subset sum problem have been shown to be $NP$ complete. Unlike the knapsack problem, which is an optimization problem, the subset sum problem is a decision-problem.
I came across a problem that is closely related to a knapsack problem except that it is of a higher dimension. For simplicity, we first consider the subset sum problem in a higher dimension representation and see if $NP$ complete complexity holds true. Then we will proceed to the optimization aspect.
First let us describe the subset sum problem. Given a set $S$ is there a subset $S' \subseteq S$ such that $k = \sum_{s\in S'} s$? This problem is a true decision problem, as we are asked if such a subset $S$ exists.
On to the knapsack problem. We consider three models for the knapsack problem:- 0-1 knapsack problem. Given a set of $n$ items, each with the weight $w_i $ and value $v_i $, where $i = 1 \ldots n$ and if the max weight of the knapsack is $W$. We would like to maximize: $\sum_{i=1}^n v_i x_i $ which is subject to $\sum_{i=1}^n w_i x_i \le W$ and $x_i \subseteq \{0,1\}$.
- Bounded Knapsack Problem (BKP). What if we have multiple $x_i$? In otherwords, there can be more than one copy of $x_i$. In which we'd be trying to maximize $\sum_{i=1}^n v_i x_i $ and subject to $\sum_{i=1}^n w_i x_i \le W$ and $x_i \subseteq \{0,\ldots, c_i\}$.
References
- Cormen, Thomas et al. Introduction to Algorithms, Third Edition.
- Garey, Michael R. and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences).