public
Last active

js :: knapsack problem subset (coin problem)

  • Download Gist
coin-amount.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
(function (amount, coins) {
'use strict';
var n = coins.length,
cc = function cc(aMoney, aCoins, arr) {
var tempArr;
if (aMoney < 0 || aCoins.length === 0) {
return 0;
} else if (aMoney === 0) {
console.log(arr);
return 1;
} else {
tempArr = arr.slice(0);
tempArr.push(aCoins[0]);
return cc(aMoney - aCoins[0], aCoins, tempArr) + cc(aMoney, aCoins.slice(1), arr);
}
};
console.log(cc(amount, coins, []));
}(10, [5, 1, 2]));
gistfile1.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
(function (amount, coins) {
'use strict';
var n = coins.length,
sum = function (arr) {
return arr.reduce(function (previousValue, currentValue, index, array) {
return previousValue + currentValue;
}, 0);
},
count = function count(target, arr) {
var i, temp = 0, tempArr;
if (target < 0) {
return 0;
} else if (target === 0) {
console.log(arr + ' = ' + sum(arr));
return 1;
}
for (i = 0; i < n; i += 1) {
tempArr = arr.slice(0);
tempArr.push(coins[i]);
temp += count(target - coins[i], tempArr);
}
return temp;
};
console.log(count(amount, []));
}(10, [1, 2, 5]));

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.