Decreasing values in an array

general
, ,
1

We are 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.

To summarize, player A and B are alternating and decreasing values of elements of an array, what is the optimal strategy for A with which he can achieve the maximal amount of reward points?

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.

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?