> For Scenario 1 (just two traits), he solved it exactly using dynamic programming.

I wonder if this exact solve tried setting "more rejections than X" as failure, so that you can get better best case for the cost of dropped worst cases