How to solve this?

Revision en1, by bruh_wtf_lmao, 2021-01-16 04:44:49

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!

Tags #help, mitm


  Rev. Lang. By When Δ Comment
en2 English bruh_wtf_lmao 2021-01-16 04:45:43 0 (published)
en1 English bruh_wtf_lmao 2021-01-16 04:44:49 468 Initial revision (saved to drafts)