Determine the optimal strategy and maximize the reward

Question

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:

1. Round 1: Player A skips this round, player B picks arr[1] and therefore decreases it's size by his strength (now arr[1] = (1,2)).
2. Round 2: Player A picks and finishes arr[1] (playerA.reward += 2), player B picks arr[2] (arr[2] = (2,3))
3. Round 3: Player A picks and finishes arr[2] (playerA.reward += 3), player B picks arr[0] (arr[0] = (4,5))
4. 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.

Answer 1

The key observation is that, for player A, picking an object which is not being picked by player B is equivalent to skipping the turn and saving this pick for later (for example use a variable savedPicks). Now instead of having to decide upon which object to pick the problem becomes deciding if player A should pick the current object picked by player B or save the pick for later. So we iterate through the objects depending on how player B picks them and either also pick the object as he does or save a pick for later.

Now the problem is solvable with DP, observe that your state consists of the current object which is targeted by player B, the remaining size of the object and the number of picks player A has saved.

There are three transitions:

1. Object is finished, move to the next one,
2. Player A skips the round and saves a pick for later (savedPicks++),
3. Player A uses a saved pick to pick the current object (potentially getting the reward if his pick finished the current object).

Solve each of the three transitions, apply memoization (save already computed states, use a 3 dimensional array for example), don't forget the base case (all objects have been finished).

Happy coding!