# Decreasing values in an array

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?