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!

#### История

Правки

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)