The trick for Scenarios 2 and 3 is that most of the constraints don't end up being bottlenecks. For example in Scenario 2, well-connected pretty much always gets satisfied while doing the other constraints, so the DP table only needs 4 dimensions (space, Berlin local, techno lover, creative).
My other trick was to only build the full DP table for the latter half of the game (i.e. when all the constraints are at least 50% satisfied) which across 4 dimensions reduces the size by a factor of 16. For the beginning half of the game I combined Berlin and techno into a single parameter, which technically isn't perfect but doesn’t matter too much in the early game. I wrote up my approach here if you want more details: https://chriskw.xyz/2025/09/16/Berghain/
Re: optimizing for best case vs expected case, I thought about that but in simulations my strategy mostly performed the same as a "perfect knowledge" strategy where you could see all of the people in line ahead of time and retroactively accept people. When it under performed it was usually because some miraculous string of people showed up near the end, but betting on that happening seemed like it would do more harm than good, i.e. it would throw away more best case scenarios than it would salvage.
My other trick was to only build the full DP table for the latter half of the game (i.e. when all the constraints are at least 50% satisfied) which across 4 dimensions reduces the size by a factor of 16. For the beginning half of the game I combined Berlin and techno into a single parameter, which technically isn't perfect but doesn’t matter too much in the early game. I wrote up my approach here if you want more details: https://chriskw.xyz/2025/09/16/Berghain/
Re: optimizing for best case vs expected case, I thought about that but in simulations my strategy mostly performed the same as a "perfect knowledge" strategy where you could see all of the people in line ahead of time and retroactively accept people. When it under performed it was usually because some miraculous string of people showed up near the end, but betting on that happening seemed like it would do more harm than good, i.e. it would throw away more best case scenarios than it would salvage.