Return to Question

You have a ticket allowing you to visit up to n of M carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but you can only win once, and you have to accept the first reward that you win. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of n of M booths.

What would be a more computationally feasible way to formulate the problem?

You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but you can only win once, and you have to accept the first reward that you win. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of $n$ of $M$ booths.

What would be a more computationally feasible way to formulate the problem?

You have a ticket allowing you to visit up to n of M carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but once you win a reward you may not visit any more booths. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of n of M booths.

What would be a more computationally feasible way to formulate the problem?

You have a ticket allowing you to visit up to n of M carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but you can only win once, and you have to accept the first reward that you win. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of n of M booths.

What would be a more computationally feasible way to formulate the problem?

You have a ticket allowing you to visit up to n of M carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but once you win a reward you are finished playing. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of n of M booths.

What would be a more computationally feasible way to formulate the problem?

You have a ticket allowing you to visit up to n of M carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but once you win a reward you may not visit any more booths. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of n of M booths.

What would be a more computationally feasible way to formulate the problem?