Skip to content

Instantly share code, notes, and snippets.

@ZJONSSON

ZJONSSON/README.md

Last active Aug 29, 2015
Embed
What would you like to do?
Optimal denominations

This small script uses combinatory analysis to figure out the optimal denominations for given number of possible coins to minimize the coins required to produce any amount between 1 cent and 1 dollar. The candidate set of denominations is reduced to keep the combinatory possibilities within reason.

// Candidate denominations
var candidates = [0.02,0.03,0.04,0.05,0.06,0.7,0.08,0.09,0.10,0.12,0.13,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.60,0.7,0.8,0.9,1];
// All amounts between one cent and a dollar
var amounts = Array
.apply(0, Array(100))
.map(function (element, i) {
return (i+1)/100;
});
// Standard combinatory function
function comb(c) {
var n = candidates.length;
var s=[];
function bitprint(u) {
var s=[];
for (var n=0; u; ++n, u>>=1)
if (u&1) s.push(candidates[n]);
return s;
}
function bitcount(u) {
for (var n=0; u; ++n, u=u&(u-1));
return n;
}
for (var u=0; u<1<<n; u++)
if (bitcount(u)==c)
s.push(bitprint(u));
return s;
}
// Roll through all combinations and pick minimum score
function denom(n) {
return comb(n-1)
.reduce(function(p,c) {
c = c.sort().reverse().concat(0.01);
var score = amounts.reduce(function(p,s) {
return p + c.reduce(function(p,d) {
if (s > 0) {
p += Math.floor(s/d);
s = s % d;
}
return p;
},0);
},0);
return (p && p.score < score) ? p : { score: score, denom: c};
});
}
<!DOCTYPE html>
<meta charset="utf-8">
<h1>Optimal denominations for a dollar</h1>
<script src="denom.js"></script>
<script>
var numCoins = [2,3,4,5,6];
function next() {
var n = numCoins.shift();
if (!n) return;
var result = denom(n);
var res = document.createElement('p');
res.textContent = n+' coins is: '+JSON.stringify(result.denom)+' with a score of '+result.score;
document.body.appendChild(res);
setTimeout(next)
}
setTimeout(next)
</script>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment