Complexity of Brute Force Knapsack Problem?

Question

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 ?

Answer 1

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.