I’ve quickly implemented an bottom up solution that should work with any number of coins and should output the optimal solution:
public class CoinStack
{
public int coinValue;
public int totalCount;
public CoinStack next = null;
public override string ToString()
{
if (coinValue == 0)
return "No solution";
var sb = new System.Text.StringBuilder();
sb.Append(coinValue);
for (var cur = this.next; cur != null && cur.coinValue > 0; cur = cur.next)
sb.Append(", ").Append(cur.coinValue);
return sb.ToString();
}
public CoinStack[] Tally()
{
Dictionary<int, CoinStack> dict = new Dictionary<int, CoinStack>();
for (var current = this; current != null && current.coinValue > 0; current = current.next)
{
CoinStack c = null;
if (!dict.TryGetValue(current.coinValue, out c))
{
c = new CoinStack { coinValue = current.coinValue, totalCount = 0 };
dict.Add(current.coinValue, c);
}
c.totalCount++;
}
var values = dict.Values;
CoinStack[] result = new CoinStack[values.Count];
values.CopyTo(result,0);
return result;
}
}
public class CoinDB
{
private int[] coins;
private List<CoinStack> stack = new List<CoinStack>();
public CoinDB(params int[] aCoins)
{
coins = aCoins;
stack.Add(new CoinStack { coinValue=0, totalCount=0 });
}
public CoinStack GetChange(int aAmount)
{
if (aAmount < 1)
return null;
// requested number not yet in our DB
if (aAmount >= stack.Count)
{
// add missing values up to our current amount
for (int i = stack.Count; i <= aAmount; i++)
{
var newNode = new CoinStack { totalCount = aAmount + 1 };
stack.Add(newNode);
for (int n = 0; n < coins.Length; n++)
{
int coinValue = coins[n];
int remainder = i - coinValue;
// if the remainder is negative, there's no solution with this coin, so try the next
if (remainder < 0)
continue;
var prev = stack[remainder];
// if the remainder amount does not have a solution, try the next coin
if (prev.totalCount == -1)
continue;
// found solution of length "count"
int count = prev.totalCount + 1;
if (count < newNode.totalCount)
{
// the new solution is better than the old one, so replace it
newNode.coinValue = coinValue;
newNode.next = prev;
newNode.totalCount = count;
}
}
// if after we tried all coins we still have no solution, there is no solution for this value
if (newNode.coinValue == 0)
{
newNode.totalCount = -1;
}
}
}
return stack[aAmount];
}
}
Note the CoinDB class is meant to be created once for a set of coins. It will remember all intermediate values. You can call the “GetChange” method several times and the internal DB will grow if necessary. Yes, finding the optimal solution requires some memory, however it’s not that much after all. The CoinStack instances will form a tree of nodes which when traversed give you the actual solution. I’ve added the “Tally” method to actually count each individual coin and provide a compact solution.
I’ve even tried it with a value around 1 million and it performs well on my pc. (ps: it takes almost 30000 coins with value of 35 to get over a million ^^).
My test code currently looks like this:
var sw = new System.Diagnostics.Stopwatch();
sw.Start();
var coinDB = new CoinDB(35, 17, 11, 8, 5);
var res = coinDB.GetChange(1046873);
sw.Stop();
var getChangeTime = sw.ElapsedMilliseconds;
sw.Start();
Debug.Log("CompleteSolution: " + res);
sw.Stop();
var debugPrintTime1 = sw.ElapsedMilliseconds;
sw.Start();
var coinList = res.Tally();
sw.Stop();
var TallyTime = sw.ElapsedMilliseconds;
sw.Start();
foreach (var c in coinList)
{
Debug.Log(""+c.totalCount + " x " + c.coinValue);
}
sw.Stop();
var debugPrintTime2 = sw.ElapsedMilliseconds;
Debug.Log(
"getChangeTime: " + getChangeTime + "
"+
"debugPrintTime1: " + debugPrintTime1 + "
" +
"TallyTime: " + TallyTime + "
" +
"debugPrintTime2: " + debugPrintTime2 + "
");
ps: the value of “1046873” can be split up into
29910 x 35
1 x 8
3 x 5
pps: don’t try too many of those large numbers as the “CompleteSolution” debug log will actually log 29910 times the string "35, " into the editor log. The console window will trucate the message.
