cs6515 hw2 Rules of the Game
Rules of the Game
You have been invited to participate in a new game created by Head TA Jamie.
Jamie gives you a list of tasks that you may choose to attempt or skip.
• The ith task has a point value of P [i]
• The ith task has a success rate of S[i] where 0.0 <= S[i] <= 1.0
• You start with a multiplier value x and an increment value y
Starting from task 1, you may choose to attempt or skip a task. This will affect your final score.
1. If you succeed, your score will be increased by the point value times the current multiplier.
2. If you fail, your score will be deducted by half the point value, ignoring the multiplier.
3. To add a bit of strategy to the game, every task you skip increments the multiplier by y.
4. Each time you attempt a task, the multiplier is reset to x after the attempt.
To play the game, you are given the following:
• A list of point values P for n tasks, with non-negative values.
• A list of success rates S for n tasks, with non-negative values.
• A non-negative x as the initial multiplier.
• A non-negative y as the multiplier increment.
Develop an efficient dynamic programming algorithm to determine the maximum expected value and which tasks you should attempt to achieve it.
• You start with zero points.
• The list of attempted tasks must be in the same order that you received them.
Implement your algorithm for solving this problem in cs6515_rules__game.py.