Algorithm for simple board game

We have N coins of type-1 and M coins of type-2. A game-board has N squares of type-1 and M squares of type-2. In this game we must place one coin into each square. After placing all coins we will get a score based on our coin placement strategy .

If type-1 square contains a type-1 coin then we will get A points, if type-2 square contains a type-2 coin then we will get B points and in all other cases, we will get C points.Our total game score will be sum of scores of all squares.

Inputs Available are ( N,M,A,B,C )

How can we maximize our score ?

Quote:

---

Originally Posted by aakashjsr

How can we maximize our score ?

---

We can start by putting all N type-1 coins on the N type-1 squares and all M type-2 coins on the M type-2 squares. The score becomes,

Score = N*A + M*B + 0*C

Can we improve on this? Yes we can swap one type-1 coin with one type-2 coin. The score becomes,

Score = (N-1)*A + (M-1)*B + 2*C

Did it pay off? Well we lost A+B but gained 2*C so if

2*C > A+B

we gained more than we lost. And if we gained something by this one-coin swap we can gain even more by swapping as many coins as possible.

So first we must find out whether swapping pays off at all (otherwise we already have the maximum score). If it pays off indeed we must figure out what is the biggest swap we can make and calculate the score for that.

this is a simple math problem.

all coins into the 'right' squares gives a total score of N*A+M*B

as many coins as possible into the 'wrong' squares is 2*min(N,M)*C + (N-min(N,M))*A + (M-min(N,M))*B

follow whichever of the above 2 possibilities gives the highest value