Function minCoinsChange

src/others/min-coins-change.js:25–44

* Returns the minimum number of coins from given set, * which sum equals to given change. This is famous * problem from the dynamic programming: * https://en.wikipedia.org/wiki/Change-making_problem * * @public * @module others/minCoinsChange * * @example * * v

(coins, change)

   *  list, required for the change.
   */
  function minCoinsChange(coins, change) {
    var minChange = [[0]];
    if (coins.indexOf(change) >= 0) {
      return [change];
    }
    for (var i = 1; i <= change; i += 1) {
      for (var j = 0; j < coins.length && coins[j] <= change; j += 1) {
        for (var k = 0; k < minChange.length; k += 1) {
          if (k + coins[j] === i) {
            minChange[i] = minChange[k].concat([coins[j]]);
          }
        }
      }
    }
    var result = minChange[change];
    if (!result) {
      return undefined;
    }
    return result.slice(1);
  }

  exports.minCoinsChange = minCoinsChange;