JSFiddle - React, Tailwind, and code Playground
JavaScript
// Candidate denominations
var candidates = [0.02,0.03,0.05,0.07,0.11,0.13,0.17,0.19,0.23,0.29,0.31,0.37,0.41,0.43,0.47,0.53,0.59,0.61,0.67,0.71,0.73,0.79,0.83,0.89,0.97,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};
});
}
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)