var MONEYS = [ 1000, 500, 100, 50, 10, 5, 1]; var MAX_PAY = 1000; function min_coins(money) { if (money === 0) { return []; } coin = _(MONEYS).find(function (coin) { return coin <= money; }); return [coin].concat(min_coins(money - coin)); } var money_to_coins = _.reduce(_.range(0, MAX_PAY * 2), function (h, m) { h[m] = min_coins(m); return h; }, {}); function good_pay(need) { return _.chain(_.range(need, MAX_PAY * 2)).sortBy(function (pay) { // 支払い枚数とお釣り枚数の合計で並べ替える // このへんでスコアを計算するようにすると任意の戦略でソートできる return money_to_coins[pay].length + money_to_coins[pay - need].length; }).map(function (pay) { return { pay: pay, pay_coins: money_to_coins[pay], ret_coins: money_to_coins[pay - need] }; }).value(); } function coin_counts(coins) { return _.reduce(coins, function (h, v) { if (!h[v]) { h[v] = 0; } h[v] += 1; return h; }, {}); } function coin_counts_msg(coins) { counts = coin_counts(coins) return _.chain(MONEYS).filter(function(m) { return counts[m] }).map(function(m) { return m + '円x' + counts[m]; }).value().join(', '); } var inputElem = document.getElementById('good-pay-need'); var resultElem = document.getElementById('good-pay-result'); var template = _.template("<td><%= pay %>円</td><td><%= pay_count %>枚(<%= pay_count_msg %>)</td><td><%= ret_count %>枚(<%= ret_count_msg %>)</td><td><%= pay_count + ret_count %>枚</td>"); function update() { while (resultElem.firstChild) { resultElem.removeChild(resultElem.firstChild); } var tr = document.createElement('tr'); tr.innerHTML = '<tr><th>支払い金額</th><th>支払い枚数</th><th>お釣り枚数</th><th>合計枚数</th></tr>'; resultElem.appendChild(tr); var input = inputElem.value; if (input && input.match(/^\d{1,3}$/)) { var need = parseInt(input, 10); _.each(good_pay(need).slice(0, 5), function (result) { var tr = document.createElement('tr'); tr.innerHTML = template({ pay : result.pay, pay_count : result.pay_coins.length, ret_count : result.ret_coins.length, pay_count_msg : coin_counts_msg(result.pay_coins), ret_count_msg : coin_counts_msg(result.ret_coins), }); resultElem.appendChild(tr); }); } } inputElem.addEventListener('keyup', _.throttle(update, 1000)); update();