Given an array of length n
filled with objects which contain 2 ints (size
and reward
).
Now 2 players are taking turns, each player has an int value we call strength
. Let's call them player A and player B, player A goes first.
Player A can pick whichever object from the array he wants and decrease the size
of the object by his strength
(pickedObj.size -= playerA.strength
), he can also skip his turn by simply not picking an object.
Player B is simple minded and for all his turns uses the same greedy strategy: he picks the object with the smallest size
and decreases it's size
by his strength
(pickedObj.size -= playerB.strength
), player B can't skip turns.
Once a player decreases the size
of an object to 0 (or bellow) he receives the reward (playerX.reward += finishedObj.reward
) associated with that object. Each player starts with 0 reward points (playerX.reward = 0
).
Given an array with n
objects, player A with strength = m
and player B with strength = k
, compute the maximal amount of reward points
that player A can win.
Examples:
Example 1:
obj[] array = `{ (9,5), (6,2), (7,3) }`;
playerA.strength = 4;
PlayerB.strength = 5;
int solution = determineMaxReward(array, 4, 5);
// The solution (max amount of money player A can win) is 10.
Explanation:
- Round 1: Player A skips this round, player B picks
arr[1]
and therefore decreases it'ssize
by hisstrength
(nowarr[1] = (1,2)
). - Round 2: Player A picks and finishes
arr[1]
(playerA.reward += 2
), player B picksarr[2]
(arr[2] = (2,3)
) - Round 3: Player A picks and finishes
arr[2]
(playerA.reward += 3
), player B picksarr[0]
(arr[0] = (4,5)
) - Round 4: Player A picks and finishes
arr[0]
(playerA.reward += 5
)
That's an optimal game for player A, the at the end he is left with 10 reward points which is the maximal amount of reward points he can possibly achieve.
Example 2:
obj[] array = `{ (2,1), (2,5) }`;
playerA.strength = 1;
PlayerB.strength = 2;
int solution = determineMaxReward(array, 1, 2);
// The solution (max amount of money player A can win) is 5.
Example 3:
obj[] array = `{ (9,3), (10,3), (4,1), (8,1), (9,2) }`;
playerA.strength = 5;
PlayerB.strength = 3;
int solution = determineMaxReward(array, 5, 3);
// The solution (max amount of money player A can win) is 10.
My current unproven (in the sense of optimality) approach:
For each object, I compute the minimal number of picks player A needs to make in order to finish that object. Then I reduce to the knapsack problem, size of the knapsack being the number of picks player A can do during the game, then the best way to fit the objects with their size and reward into the knapsack (such that the reward is maximized) is found.
Now I'm not sure if this is optimal, I can't find a counterexample where my approach doesn't work but I also can't prove that it's optimal. Any help/comments are appreciated.
This is a problem I have been struggling with for a while now, I encountered it during a programming contest in the context of dynamic programming.