You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
49 lines
1.4 KiB
JavaScript
49 lines
1.4 KiB
JavaScript
(function (exports) {
|
|
'use strict';
|
|
|
|
/**
|
|
* Returns the minimum number of coins from given set,
|
|
* which sum equals to given change. This is famous
|
|
* problem from the dymanic programming:
|
|
* {@link https://en.wikipedia.org/wiki/Change-making_problem}
|
|
*
|
|
* @public
|
|
* @module others/minCoinsChange
|
|
*
|
|
* @example
|
|
*
|
|
* var minCoinsChange =
|
|
* require('path-to-algorithms/src/others/min-coins-change')
|
|
* .minCoinsChange;
|
|
* var coins = minCoinsChange([1, 2, 3], 5); // [ 2, 3 ]
|
|
*
|
|
* @param {Array} coins The sorted list of the coins used for the change.
|
|
* @param {Number} change The change, which should be returned.
|
|
* @return Array which contains the minimum coins from the given
|
|
* 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;
|
|
|
|
})(typeof window === 'undefined' ? module.exports : window);
|