# Strategy/algorithm to divide pot to chips

I want to split poker pot to chips.

Example:

Pot = \$17.500.

I have the endless piles of chips. I have the following types of chips: ChipsTypes = [\$1, \$5, \$10, \$25, \$100, \$500, \$1.000, \$5.000, \$10.000, and so on]. Index starts from 0.

I want to get an array that says which chips I have to take to divide the pot and in which order to have minimum number of denominations and chips after pot-to-chips conversion. For example Result = [7, 5] means that I have to take 3 * \$5.000 + 5 * \$500 which \$17.500.

Is there is any strategy or algorithm that would suit my need?

• "Result = [7, 5] means that I have to take 3 * \$5.000 + 5 * \$500" eh? Jul 19, 2012 at 16:16
• Is this homework, it sure seems like it. Jul 19, 2012 at 16:44
• It's unclear what you mean by "which chips I have to take to divide the pot" Jul 19, 2012 at 16:46
• How are you weighting the number of denominations vs. the number of chips? With your \$17,500 example, we have several valid solutions. 1-10k, 1-5k, 2-1k, 1-500 (5 chips, 4 dens) or 3-5k, 2-1k, 1-500 (6 chips, 3 dens) or 17-1k, 1-500 (18 chips, 2 dens), etc... What's the optimal weighting? The first two solutions have an equal sum of chips and denominations, so are they equivalent in being correct?
– user53019
Jul 26, 2012 at 20:02
• @Baqueta - period is used rather than comma in some locales as a thousands/millions/billions delimited. Jul 27, 2012 at 18:31

It sounds to me like you are attempting to solve the Knapsack Problem if you want a general solution where any denominations would work.

Put in those terms this is an unbounded knapsack problem where all the values are -1 and the weights are the denomination of the chip.

You should be able to find lots about the problem online.

• More specifically, it is the change-making/coin-change problem. While it is definitely analogous to the knapsack problem, it can be a little tough wrapping your head around the algorithm while thinking in terms of knapsacks and weight. Jul 27, 2012 at 22:39

In general, since this seems like a homework question and I don't want to give away the answer, here's the strategy to solving the problem.

• Find the largest denomination at or below the value of the pot and divide the pot by that denomination
• That's how many of that denomination of chip you require
• Take the remainder of the pot, and repeat these steps until the pot is \$0.00

For example

``````   17.5 / 10 = 1 with 7.5 remaining (we need one \$10 chip)
7.5 / 5  = 1 with 2.5 remaining (we need one  \$5 chip)
...etc
``````

...it appears I still pretty much gave away the answer.

• This is straightforward approach which will definitely work but will result with many different denominations. It is already implemented by me. I am looking for strategy that will give me required/preferred number of denominations. Jul 20, 2012 at 4:10
• If you want fewer types of chips, and are using the denominations you list in your question, start with Chad's algorithm and then look for chances to "break" larger chips into smaller ones, i.e. if you've got one \$20 and a \$5 chip, and want them all in the same denomination, split the \$20 into four \$5's. Jul 20, 2012 at 7:47
• @MinimeDJ, you said you wanted "minimum number of denominations and chips", I gave you the way to get the minimum number of chips. To reduce denominations, you would need to look at any "small" stacks, and break it down to a smaller denomination that you already contain. Jul 20, 2012 at 13:35
• @Chad: Your greedy algorithm does not work for all denominations. For example, if we the we only have \$5, \$20 and \$25 chips available then the greedy algorithm would split \$40 into [\$25, \$5, \$5, \$5] instead of the optimal [\$20, \$20]. Jul 20, 2012 at 17:30
• @missingno, no casino would ever have a \$20 and \$25 dollar chip in the same game... Jul 20, 2012 at 17:51

In general this problem can be stated as integer programming problem. So the task is

x_i = how many chip type i you have

maximize:

sum(-x_i)

subject to:

sum(chipvalue_i*x_i)=pot

x_i >= 0 and x_i is integer for all i

In general this kind of problems are NP-hard. But if the pot size isn't too big one relatively easy algorithm for the problem is so called branch-and-bound algorithm. For explanation of the algorithm see: http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf, Chapter 9.5, page 289

O(n*c) dynamic programming algorithm in pseudocode, where n is the amount of money in dollars (or cents, if there are any chip values with a cent portion), and c is the number of chip sizes. Returns 0 if no chip formulation is found. This only provides the count of the chips. To get the actual chip counts, replace MoneyArray with an array of Lists of chipsizes, and mincount with a List of chipsizes.

``````fun GetMinChipCount(Array ChipSizes, Int MoneyCount)
MoneyArray = Int[1..MoneyCount]
for i = 1 to MoneyCount:
Int mincount = 0
foreach Chip in ChipSizes:
if Chip < i: continue
if Chip = i: mincount = 1
if Chip > i
Int CountVal = MoneyArray[Chip-i]
if CountVal = 0: continue;
if mincount == 0 or mincount > CountVal + 1: mincount = CountVal + 1
MoneyArray[i] = mincount;
return MoneyArray[MoneyCount]
``````
• Dynamic programming is definitely the correct approach. It is worth mentioning that, depending on the chip denominations, you may have multiple optimal solutions for a given pot size. If you require a result that returns all of the optimal solutions, you'll have to modify the result array (in this case, `MoneyArray`) to store a list of solutions (which will be arrays themselves). Jul 27, 2012 at 22:30

What you describe is less a "pot to chips" algorithm (in real poker, the winner simply rakes in the chips from the center of the table) and more of a "coloring up" algorithm (once a player's ready to leave, he gives his stash to the banker who reduces the chips to the minimum number required), which is basically a "change-making" algorithm using amounts larger than \$1.00.

Here's how I would write it in C#:

``````//I convert this enum to an array of its values, so you could skip this
public enum ChipDenom : int
{
One = 1,
Five = 5,
Ten = 10,
TwentyFive = 25,
OneHundred = 100,
FiveHundred = 500,
OneThousand = 1000,
FiveThousand = 5000,
TenThousand = 10000
}

public Dictionary<ChipDenom, int> ColorUp(int chipAmount)
{
int remainingAmount = chipAmount;

//you could instead define an int[] containing the dollar values;
var chipValues = Enum.GetValues()
.OfType<ChipDenom>()
.OrderByDescending(cd=>cd)
.ToArray();

//If you do, the return value of this method should be Dictionary<int,int>
var result = new Dictionary<ChipDenom, int>();

while(remainingAmount > 0)
{
//find the largest chip denomination less than the remaining amount
var highest = chipValues.First(cd=>(int)cd < remainingAmount);

//determine how many of that chip can be used
var quantity = remainingAmount / (int)highest;

//and add it to the chip stack

//and repeat with whatever's left over
remainingAmount %= (int)highest;
}

return result;
}

...

//Usage:

var winnings = 13579;

//to determine the chips to give to a single player:
var chips = ColorUp(winnings);

foreach(var kvp in chips)
Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value)

//to determine the chips to give to X players who split the pot:
var splitPlayers = 3;
var winnings = 13579;

var leftOver = winnings % splitPlayers;

var winningsPerPlayer = winnings / splitPlayers;

var playerChips = ColorUp(winningsPerPlayer);
var tableChips = ColorUp(leftOver);

foreach(var kvp in playerChips)
Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value);

Console.WriteLine("Leave in pot:");

foreach(var kvp in tableChips)
Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value);
``````

A brute force approach is to modify @Chad's basic algorithm, but then once you have found a solution, start again but with one less chip in the pile of the biggest denomination left. Then rinse and repeat and throw away which ever result is less desirable. The end condition is where you run out of chip denominations, or you know you will always have more chips.

Simply trying to break chips apart doesn't take into account the divisibility of the chips, they could have no common factor (although they do in the example above).

So assuming you have to split \$37 and you have some weird chips sizes:

\$22, \$10, \$7, \$1

```Decrement 22's
22*1 + 10*1 + 7*0 + 1*5  = 37 with 7  chips

Decrement 10's
22*0 + 10*3 + 7*1 + 1*0  = 37 with 4  chips
22*0 + 10*2 + 7*2 + 1*3  = 37 with 7  chips
22*0 + 10*1 + 7*3 + 1*6  = 37 with 10 chips

Decrement 7's
22*0 + 10*0 + 7*5 + 1*2  = 37 with 7  chips
22*0 + 10*0 + 7*4 + 1*9  = 37 with 13 chips
22*0 + 10*0 + 7*3 + 1*16 = 37 with 19 chips
22*0 + 10*0 + 7*2 + 1*23 = 37 with 25 chips
22*0 + 10*0 + 7*1 + 1*30 = 37 with 31 chips
22*0 + 10*0 + 7*0 + 1*37 = 37 with 35 chips
```
• +1 I like the "incremental" approach to this. Brute force or not, this is most likely will solve the problem. It will also provide all multiple best answers. Jul 26, 2012 at 8:13
• Just to check, what if I had to split \$37 and had weird chip sizes of: \$22, \$21, \$9, \$7, \$2, \$1 - would this algorithm find the \$21, \$9, \$7 solution? Jul 26, 2012 at 12:20
• @David_001: Probably, because they are in a row, but at first glance it looks like a solution like a,2xc,e in a-e could be missed. Jul 26, 2012 at 15:04

``````using System;

namespace MinimumStack
{
public class Node
{
public static long[] denominations = { 1L, 5L, 10L, 25L, 50, 100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L, 100000L, 500000L, 1000000L, 5000000L, 10000000L, 250000000L, 500000000L, 100000000L, 500000000L, 1000000000L };
public long Data { get; set; }

public long Denom { get; set; }
public long Denom1 { get; set; }
public long Denom2 { get; set; }

public int denomChip1 { get; set; }
public int denomChip2 { get; set; }

public long ChipCount { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node()
{

}
public Node(long data,int index,long chipCount1)
{
this.Data = data;
this.ChipCount = chipCount1;

if(index > 0)
{
this.Denom = denominations[index+1];
this.Denom1 = denominations[index];
if(data >= denominations[index] && data >0)
{
long chipcount1 = data / denominations[index];

long newdata = data - denominations[index] * chipcount1;
//if(newdata>0)
Left = new Node(newdata, index - 1, chipcount1);
}
}

if( index-1 > 0)
{
this.Denom2 = denominations[index - 1];

if(data>= denominations[index-1] && data > 0)
{
long chipcount1 = data / denominations[index-1];
Console.WriteLine(data+ " data ======== " +denominations[index-1]+" = "+chipcount1);
long newdata = data - denominations[index-1] * chipcount1;
//if(newdata>0)
Right = new Node(newdata, index - 2, chipcount1);
}
}

if(index == 0)
{

//this.ChipCount = data;
this.Denom = denominations[index+1];
this.Denom1 = denominations[index];
Left = new Node(0, index - 1, data);
}
if(index-1 == 0)
{

//this.ChipCount = data;
this.Denom2 = denominations[index-1];
Right = new Node(0, index - 2, data);
}

//Console.WriteLine("===========================*************=====================================");

//            Console.WriteLine("===============================******************=================================");

}

/*
private void InsertRec(Node root, Node newNode)
{
if (root == null)
root = newNode;

if (newNode.Data < root.Data)
{
if (root.Left == null)
root.Left = newNode;
else
InsertRec(root.Left, newNode);

}
else
{
if (root.Right == null)
root.Right = newNode;
else
InsertRec(root.Right, newNode);
}
}
*/
}
public class Program
{
private Node _root;
public static void Main(string[] args)
Program p = new Program();
long amount = 14;//15L;
long[] str1 = { 1L, 5L, 10L, 25L, 50L, 100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L, 100000L, 500000L, 1000000L, 5000000L, 10000000L, 250000000L, 500000000L, 100000000L, 500000000L, 1000000000L };
//Console.WriteLine("Hello, world!" + p.GetMaxDenomination(44440L));
for (int j = str1.Length - 1; j >= 0; j--)
{
if (amount >= str1[j] && str1[j] > 1)
{
Console.WriteLine((4/1)+"Hello, world! " +j);
p._root = new Node(amount, j, 0L);
break;
}
}
p.DisplayTree();
Console.WriteLine("Do something test "+ 44440L/10L);
Console.WriteLine("================================================================");
// p.DoSomething();
}
private void DisplayTree(Node root,long count)
{
if (root == null)
{
// Console.WriteLine("ChipCount "+count);
return;
}
//Console.WriteLine("Denom " +root.Denom +" ChipCount " +(root.ChipCount));
if(root.Data == 0)
Console.WriteLine("ChipCount "+(count));
//  Console.WriteLine("================================================================");
if (root.Left != null)
DisplayTree(root.Left,root.Left.ChipCount+count);

/* System.Console.WriteLine(root.Data + "Root "+root.Denom1+ " : "+root.Denom2+" chipcount "+root.ChipCount+ "Chip Denomination: "+root.Denom);

if(root.Left != null)
System.Console.WriteLine(root.Left.Data + " left " +root.Left.ChipCount);
if (root.Right != null)
System.Console.WriteLine(root.Right.Data + " right "+root.Right.ChipCount);
*/
if (root.Right != null)
DisplayTree(root.Right,root.Right.ChipCount+count);
//  Console.WriteLine("================================================================");
}
public void DisplayTree()
{
DisplayTree(_root,_root.ChipCount);
}
public long GetMaxDenomination(long value)
{
long[] denominations = {1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
long maxDenomination = denominations[0];
for (int i = 1; i < denominations.Length; i++)
{
float val = value/denominations[i];
Console.WriteLine("value "+ val);
if (val > 0)
{
maxDenomination = denominations[i];
}
}
return maxDenomination;
}

public void DoSomething()
{//{1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
long[] str1 = {1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
for(long i = 44440L;i<=44440L; i++)//1000000000L
{
// print("\(i)")
//if(i%5 == 0)
{
var amount = i;
var chipcount = 0L;
for( int j = str1.Length-1;j>=0;j--)//.reversed()
{// print(j)
if(amount/str1[j] > 0 && str1[j]>1)
{
//Console.WriteLine(str1[j]+" reach "+ amount +" here "+amount/str1[j] );
chipcount += amount/str1[j];
var k = amount/str1[j];
amount = amount - str1[j]*k;
}
else if(str1[j]==1)
{
Console.WriteLine(str1[j]+" reach "+ amount +" here "+amount );
chipcount+=amount;amount =0;
}
if(amount == 0)
break;
}
if(chipcount > 11)
{
Console.WriteLine(i+" amount will have chip "+ chipcount);
// print("\(i) amount will have chip \(chipcount)")
}
}
}
}
}
}
``````