bruh_wtf_lmao's blog

By bruh_wtf_lmao, history, 3 months 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!

Read more »

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