I got stuck on this problem in the context of dynamic programming:
There are n tasks, each of them has a time it takes to finish it and a reward (amount of money the player that finishes the task gets). The tasks are not atomic, meaning that for example a task with time 10 can be solved by spending 5 time units during 2 different rounds. So it is possible to solve a task partially but ONLY the player who finishes the task get’s the money. In other words, only the player who sets the time of the task to 0 (or bellow) gets the reward/money for that task.
There are 2 players (let’s call them A and B). Each player has a block of time which he can spend on exactly one task per round (a player can not spend his time on 2 different tasks during 1 round), players can have time blocks of different sizes. Players B strategy is always the same: on his turn during the round, he picks the task with the lowest amount of time left and spends his time block on that task. Player A can pick whichever task he wants, he can also skip rounds. During each round player A goes first (player A picks a task or skips the round, then player B picks a task).
For given:
- Player A time per round (amount of time player A can spend on exactly one task per round),
- Player B time per round (-||-),
- n tasks with T (time required to finish the task) and M (money a player gets for finishing the task),
determine the optimal strategy for A such that the amount of money he wins is maximized. Output the maximal amount of money player A can win.
Example:
Given:
- A time per round: 4
- B time per round: 5
- task1 (T=9, M=5)
- task2 (T=6, M=2)
- task3 (T=7, M=3)
The solution (max amount of money player A can win) is 10.
Explanation: round1: player A skips this round, player B picks task 2 (now task2 has T=6-5=1), round2: player A picks and finishes task 2, player B picks task 3, round3: player A picks and finishes task 3, player B picks task 1, round 4: player A picks and finishes task 1. All tasks are finished, player A is left with 5+2+3=10 money.
Can this problem be reduced to some other well-known problem? Can you explain to me how I could solve this or point me to some website which can help me to understand the solution to this problem?
This is what I have from notes/memory and is an adequate description of the problem I hope, give me a chance to clarify if any part of the problem seems unclear.