Skip to content

Instantly share code, notes, and snippets.

@robophil
Forked from KodjoSuprem/compute_change.js
Created February 7, 2017 15:14
Show Gist options
  • Save robophil/f9c764eb448c60e8ecfbf01f8dd6f58c to your computer and use it in GitHub Desktop.
Save robophil/f9c764eb448c60e8ecfbf01f8dd6f58c to your computer and use it in GitHub Desktop.
coin change problem / Knapsack problem
var coinTypes = [25, 10, 5];     
var coinNb = [8, 12, 20]; 
function computeChange(change,coinTypes, coinNb) {   
var rez = [];   
for (var i = 0; i < coinTypes.length; ++i) {       
if (coinTypes[i] === 0) continue;       
var coinsToGet = Math.floor(change / coinTypes[i]);       
if (coinsToGet > coinNb[i]) {           
coinsToGet = coinNb[i];       
}       
change -= coinsToGet * coinTypes[i];       
rez.push(coinsToGet);   
}    return rez;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment