bruh_wtf_lmao's blog

By bruh_wtf_lmao, history, 6 weeks ago, In English

Hey guys!

I was learning the "meet in the middle" technique. Is it possible to solve the 0-1 knapsack problem with it? Let's say that $$$n$$$ is the number of items, $$$c$$$ is the capacity of the knapsack and we're given $$$n$$$ pairs of weights and values. I want to know if it is possible to solve it for $$$n \leq 32$$$ and $$$c \leq 10^{12}$$$. If yes, how can we solve it? I couldn't think of anything better than $$$\mathcal{O}(2^n)$$$.

Any help is appreciated!

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Yes, it is possible to do in $$$\mathcal{O}(n 2^{n/2})$$$ using meet-in-the-middle.

Split the items into two groups of $$$\lfloor n/2 \rfloor$$$ and $$$\lceil n/2 \rceil$$$ items each, then, for both groups, for every combination of items you can take from that group, compute the total weight and value of the taken items. You'll end up with a group of $$$2^{\lfloor n/2 \rfloor}$$$ pairs, and a group of $$$2^{\lceil n/2 \rceil}$$$ pairs.

Then, for both groups, remove irrelevant pairs: you don't want it to happen that a group contains pairs $$$(w_1, v_1)$$$ and $$$(w_2, v_2)$$$ with $$$w_1 \geq w_2$$$ and $$$v_1 < v_2$$$. This can be done in linear time.

Lastly, use the two pointers technique to find for every pair $$$(w_1, v_1)$$$ from the first group the pair $$$(w_2, v_2)$$$ in the second group, such that $$$w_2 \leq c - w_1$$$ and $$$w_2$$$ is as large as possible. Output the maximum of $$$v_1 + v_2$$$ over these pairs of pairs.

You need to sort the groups of vectors, so the time complexity is $$$\mathcal{O}(2^{n/2} \log 2^{n/2}) = \mathcal{O}(n 2^{n/2})$$$.