Hello, I can’t figure out why my implementation for the KNAPSACK problem is getting TLE. I used dynamic programming with the Top-down recursive approach.
Here is my code, with de input given as example on the problem’s page: https://ideone.com/PANnMG
And here is the same code running on input I generated with the maximum problem constraints: https://ideone.com/GbFhUl
Thanks in advance.
You could try replacing map with an unordered_map.
Tried unordered_map, with a custom comparator to use pairs as keys, but then it took 4.4s instead of 2.06s . https://ideone.com/raHyug
I suspect there is something wrong with my knapsack function implementation.
I think you’re getting hashing clashes. Try replacing 31 with 32768 in the PairHash function. My timing went from 4.03s to 0.8s.
I also tried bit shifting e.first, but that made it even slower for some reason.
Using 32768 instead of 31 it got accepted
If think using right shift, if it was the case, more pairs will hash to the same value.
Well of course, but I was using a left shift, which was equivalent to multiplying by 32768.
