You have Pokemon, Poke Balls, and Ultra Balls. Pokemon is caught with probability by Poke Ball, by Ultra Ball. You can use at most one of each ball type per Pokemon. Find the largest expected catches.
If you throw both balls at Pokemon , the catch probability is (at least one succeeds). The constraint is two-dimensional: exactly Poke Balls AND exactly Ultra Balls. Standard DP is , which is . Too slow.