How to solve this?

Правка en2, от bruh_wtf_lmao, 2021-01-16 04:45:43

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!

Теги #help, mitm


  Rev. Язык Кто Когда Δ Комментарий
en2 Английский bruh_wtf_lmao 2021-01-16 04:45:43 0 (published)
en1 Английский bruh_wtf_lmao 2021-01-16 04:44:49 468 Initial revision (saved to drafts)