λ Making change - dynamic programming

======= Algorithm ======= <syntax js> function makeChange(n, coins) { var numberOfCoins = [0]; var coinUsed = [0]; // Dynamic programming, compute the coin used from 1..n. for (var i=1; i<=n; i++) { var minNumberOfCoins = n; var coin = -1; // What next coin would get to 'i' using the minimum # of coins. coins.forEach( function(c) { if (c <= i) { var min = numberOfCoins[i-c] + 1; if (min < minNumberOfCoins) { minNumberOfCoins = min; coin = c; } } }); numberOfCoins[i] = minNumberOfCoins; coinUsed[i] = coin; } // What coins were used? var change = []; var total = n; while (total > 0) { change.push(coinUsed[total]); total -= coinUsed[total]; } return change; }</syntax> ======= Support ======= <syntax js> function run(args) { var coins = Array.prototype.slice.call(args.coins); result = makeChange(args.target, coins); } // Tailspin version of forEach so that we can step into it. Array.prototype.forEach = function(f) { for (var i=0, c=this.length; i<c; i++) { f(this[i]); } }</syntax> ======= Tests ======= <syntax js> /* Unit tests… function testA() { if (!ok) { throw "Not ok." } } */ </syntax> ======= Options ======= <syntax js> { "title":"Making change - dynamic programming", "height":"440px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> #numCoins span { width: 20px; height: 20px; border: 1px solid #BBB; display: inline-block; margin-bottom: -1px; margin-right: -1px; text-align: center; } .highlight { background-color: #FDD } .current { background-color: #DDF } </style> <script src="http://d3js.org/d3.v2.js"></script> <script> /* Optional functions function globals() { return {}; }*/ function args() { var target = parseInt(document.getElementById('target').value); var coins = document.getElementById('coins').value; coins = coins.split(","); for (var i=0;i<coins.length;i++) { coins[i] = parseInt(coins[i]); } return {target:target, coins:coins}; } function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } var numberOfCoins = x.lookupInScope("numberOfCoins"); var min = x.lookupInScope("minNumberOfCoins"); var thisMin = x.lookupInScope("thisMin"); var coins = x.lookupInScope("change") || x.lookupInScope("result"); var c = x.lookupInScope("c"); var i = x.lookupInScope("i"); numberOfCoins = numberOfCoins? numberOfCoins.slice() : []; numberOfCoins.length = args().target; var coinArray = d3.select("#numCoins").selectAll("span") .data(numberOfCoins); coinArray.enter() .append("span"); coinArray .text(function(d,j){ if (typeof d === "number") { return ""+d; } else { return (i===j && typeof min === "number")? " "+min : " "; } }); // Next coin. coinArray.classed("highlight", function(d,j){return (c && j===i-c);}); coinArray.classed("current", function(d,j){return (j===i);}); document.getElementById("used").innerHTML = JSON.stringify(coins); } </script> </head> <body> Target: <input id="target" value=20 onchange="reset()"><br> Coins: <input id="coins" value="1,2,4,8" onchange="reset()"><br> Number of Coins:<br><div id="numCoins"></div><br> Coins Used: <span id="used"></span><br> </body> </html> </syntax>