Complexity of Brute Force Knapsack Problem?
I was wondering if someone could confirm my working for the complexity for 0/1 Knapsack Brute Force,
I reasoned it is $O(N\cdot2^N)$
This is because to work out all possible subsets (The way I did brute force was to compute power set then calc weight/values for each set), takes $2^N$ and then we calculate the sum of each subset of size from 1 to $N$, that takes $N\cdot2^N$.
Space complexity would be $O(2^N)$ for the total number of subsets.
But from my notes the Brute Force 0/1 Knapsack is $O(2^N)$ with space $O(N)$.
I think that is for the recursive solution but my brute force is not recursive, so is my complexity correct ?
$\endgroup$ 21 Answer
$\begingroup$I will assume that the next is the input of the problem:
- A set of non-negative numbers $\{w_1, w_2, \ldots, w_n\}$ - weights
- A set of numbers $\{v_1, v_2, \ldots, v_n\}$ - values
- A non-negative value $W$ - available volume
We want to solve something like$$\max\limits_{i} \sum\limits_{i=1}^{n} \lambda_i v_i$$$$\text{s.t.}\quad \sum\limits_{i=1}^{n} \lambda_i w_i \leq W$$
There are exactly $2^n$ subsets, and in the trivial solution we will check them all!
For $i \in \{0, 1, \ldots, 2^n-1\}$ look at the binary representation of $i$ and take the objects accordingly, i.e. if bit $b_{j-1}$ (counted from right to left) at position $j-1$ is set ($=1$) take the object $j$ to your bag. If the total weight of the subset $i$ (i.e. all the taken objects) weighs less than $W$, record the weight of the subset. If it is less than previous record - update the record. You can forget the weight now !!!
E.g. for $i = 134_{10} = 10000110_2$ you take objects indexed by $2,3, 8$ to the subset and do not take anything else.
$\endgroup$
