Edit in JSFiddle

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();