Maximize coin selection to win gameProblem: Given an unsorted array of pots containing coins. A and B play a game where they take turns and pick up a pot either from the beginning or the end of array. If A plays first, devise a strategy to help him win the game. Solution: A recursive solution for this can be as follows:
import java.util.*;
public class MaximizeCoinCollection
{
public static void main(String[] args)
{
int numPots = 6;
int[] arr = getRandomCoins(numPots);
System.out.println(findMaxCoins (arr, 0, numPots-1));
}
// The most important part to understand here is why minimum is being chosen from the recursive calls.
// This is so because the recursive calls the best sums A would choose for himself.
// Since B is also playing with full efficiency, he will do his best to minimize the A's profit.
// And so, B will choose a pot which will allow A to choose his next pot with minimum benefit.
// For example: if B has to choose from 2,10,2,4,3, then
// B will never choose 2 as that would expose 10 to A.
// Since B will always offer a minimum to A, we take the minimum from the recursive calls.
//
// But after recursion is done, then A will definitely maximize his profit
// And that is where we choose maximum
static int findMaxCoins(int[] arr, int start, int end)
{
if (start > end)
return 0;
if (start == end)
return arr[start];
int a = arr[start] + Math.min(findMaxCoins(arr, start+2, end), findMaxCoins(arr, start+1, end-1));
int b = arr[end] + Math.min(findMaxCoins(arr, start+1, end-1), findMaxCoins(arr, start, end-2));
return Math.max(a, b);
}
// Helper method to get random coins in pots
static int[] getRandomCoins(int numPots)
{
int arr[] = new int[numPots];
for (int i=0; i<numPots; i++)
{
arr[i] = 1+(int)(Math.random()*numPots*2.33);
System.out.print (arr[i]+", ");
}
System.out.println();
return arr;
}
}
Order analysis: Order of execution for the above code is exponential. It executes 4 loops in each recursive call and recursion depth is N. So order is O(4N) Example executions: Coins: 5, 2, 7, 8, Max Sum for A: 13 Coins: 1, 12, 3, 12, 6, 10, Max Sum for A: 34 Coins: 2, 8, 10, 12, 13, 3, Max Sum for A: 25 Coins: 7, 13, 10, 10, 14, 2, Max Sum for A: 31 Printing order of choosing coins: Above will be more clear if we can also print what coins are being chosen by A. Such a thing will also help A proceed with the game because just a max-sum is useless for A to actually play the game.
import java.util.*;
public class MaximizeCoinCollectionWithSteps
{
public static void main(String[] args)
{
int numPots = 6;
int[] arr = getRandomCoins(numPots);
ArrayList<Integer> l = new ArrayList<Integer> ();
int maxCoins = findMaxCoins (arr, 0, numPots-1, l);
printAns(maxCoins, l);
}
// The most important part to understand here is why minimum is being chosen from the recursive calls.
// This is so because the recursive calls the best sums A would choose for himself.
// Since B is also playing with full efficiency, he will do his best to minimize the A's profit.
// And so, B will choose a pot which will allow A to choose his next pot with minimum benefit.
// For example: if B has to choose from 2,10,2,4,3, then
// B will never choose 2 as that would expose 10 to A.
// Since B will always offer a minimum to A, we take the minimum from the recursive calls.
//
// But after recursion is done, then A will definitely maximize his profit
// And that is where we choose maximum
static int findMaxCoins(int[] arr, int start, int end, ArrayList<Integer> l)
{
if (start > end)
return 0;
if (start == end)
{
l.add(arr[start]);
return arr[start];
}
ArrayList<Integer> l1 = new ArrayList<Integer> ();
ArrayList<Integer> l2 = new ArrayList<Integer> ();
ArrayList<Integer> l3 = new ArrayList<Integer> ();
ArrayList<Integer> l4 = new ArrayList<Integer> ();
int a = arr[start] + findMaxCoins(arr, start+2, end, l1);
int b = arr[start] + findMaxCoins(arr, start+1, end-1, l2);
int c = arr[end] + findMaxCoins(arr, start+1, end-1, l3);
int d = arr[end] + findMaxCoins(arr, start, end-2, l4);
ArrayList<Integer> tmp1;
ArrayList<Integer> tmp2;
int min1;
int min2;
if (a < b)
{
tmp1 = l1;
min1 = a;
}
else
{
tmp1 = l2;
min1 = b;
}
if (c < d)
{
tmp2 = l3;
min2 = c;
}
else
{
tmp2 = l4;
min2 = d;
}
if (min1 > min2)
{
l.addAll(tmp1);
l.add(arr[start]);
return min1;
}
else
{
l.addAll(tmp2);
l.add(arr[end]);
return min2;
}
}
// Helper method to print the answer
static void printAns(int maxCoins, ArrayList<Integer> l)
{
System.out.print ("Order of choosing coins: ");
for (int i=l.size()-1; i>=0; i--)
System.out.print (l.get(i) + ", ");
System.out.println("\nMax sum = " + maxCoins);
}
// Helper method to get random coins in pots
static int[] getRandomCoins(int numPots)
{
int arr[] = new int[numPots];
for (int i=0; i<numPots; i++)
{
arr[i] = 1+(int)(Math.random()*numPots*2.33);
System.out.print (arr[i]+", ");
}
System.out.println();
return arr;
}
}
Example executions: Pots: 5, 1, 6, 6, Order of choosing coins: 6, 5, Max sum = 11 Pots: 7, 12, 9, 11, 10, 13, Order of choosing coins: 13, 11, 12, Max sum = 36 Pots: 1, 5, 13, 6, 9, 11, Order of choosing coins: 11, 1, 13, Max sum = 25 Pots: 18, 9, 3, 8, 15, 9, 5, 19, Order of choosing coins: 19, 9, 3, 15, Max sum = 46 |
Got a thought to share or found a
bug in the code?
We'd love to hear from you:
| Name: | |
| Email: | (Your email is not shared with anybody) |
| Comment: |
Facebook comments:
