Timeline for About the pseudo polynomial complexity of the KnapSack 0/1 problem
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2020 at 4:36 | comment | added | Yuval Filmus | The exhaustive search solution checks $2^n$ subsets. | |
| Nov 2, 2020 at 22:26 | comment | added | fulem | Ok. But, do you think that my misunderstanding of the relation between $n$ and $W$ in the dynamic programming solution is also the source of confusion for my third question? i.e. that the recursive KS solution is $O(2^{(2^n)})$. | |
| Nov 2, 2020 at 21:18 | comment | added | Yuval Filmus | Your questions betray a misunderstanding on the relation between $n$, $W$, and the input length in bits. I tried to dispel this confusion in my answer. | |
| Nov 2, 2020 at 21:14 | comment | added | fulem | Hi Yuval. I'm afraid i don't see how this answer any of my three questions. Could you, please, elaborate? | |
| Nov 2, 2020 at 21:02 | history | answered | Yuval Filmus | CC BY-SA 4.0 |