Javascript Coin changing / Change making algorithm

Question

So I've been trying to create a program in Javascript/jQuery that splits an amount of money into the smallest amount of dollar bills. So far the program only works with one bill, and I'm not too sure how to implement the rest and need a push in the right direction here.

var bills = [5, 10, 20, 50, 100];

while(money > 0){ // Keep deviding
    for(var i=0; i < bills.length; i++){
        if(money < bills[i])
            return "You need a $" + bills[i] + " bill to pay for your item.";
    }
}

If I run this with money = 89; it will return 100 because that's the closest bill that can pay for $89, but I want it to return 50 + 20 + 20 so it will work with money = *anything*.

EDIT: After comments I've now come so far:

while(money > 0){ // Keep deviding
    for(var i=bills.length-1; i >= 0; i--){
        if(money > bills[i] || i == 0){
            stringToReturn += " + $" + bills[i];
            money -= bills[i];
            break;
        }
    }
}

I think you need to use modulo division: en.wikipedia.org/wiki/Modulo_operation. — Uwe Ziegenhagen
– Uwe Ziegenhagen, Commented Feb 10, 2015 at 17:06
The motivation would be to ... get the largest amount first, if it doesn't fit then go to the next largest amount and keep filling the change list,. — taesu
– taesu, Commented Feb 10, 2015 at 17:10
That's a nice idea @taesu, however when I made the loop go backwards, it's now returning $50 + $20 + $20 + $5 + $5 rather than $100 if the input is 99. Will update my post with my current code. — PWL
– PWL, Commented Feb 10, 2015 at 17:21
FYI - this is the 'Knapsack problem' - en.wikipedia.org/wiki/Knapsack_problem: 'Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible' . I found a JavaScript implementation here: gist.github.com/danwoods/7496329 - but no guarantees — Jochen van Wylick
– Jochen van Wylick, Commented Feb 10, 2015 at 17:23

taesu · Accepted Answer · 2015-02-10 17:43:44Z

5

var bills = [5, 10, 20, 50, 100];
var money = mod(89);

function mod(num){
    if (num % 5 === 0){
        return num;
    }else{
        return num + 5 - num % 5
    }
}

function foo(num){
    var index = bills.length - 1;
    var splits = [];
    while (money >= bills[0]){
        if (money >= bills[index]){
           money -= bills[index];
           splits.push(bills[index]);
        }else{
            index--;
        }
    }
    return splits;
}

console.log(foo(money));

edited jsfiddle

edited Feb 10, 2015 at 17:43

answered Feb 10, 2015 at 17:23

taesu

4,5905 gold badges26 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

João Miguel Brandão Over a year ago

235 seems to say is made up of 100+100+20+20, instead of 100+100+20+10+5

João Miguel Brandão Over a year ago

Good luck, it doesn't seem to be dealing well with the 5s!

taesu Over a year ago

It was my mod func that was messing things up. should be good, but it could be more elegant.

PWL Over a year ago

Yes, this seems very good! However, if the bills are [5, 17, 29, 70, 158] and input is 200 it returns 158,29,5,5 which is a total of 197. Any way of this to work with universal values as well?

taesu Over a year ago

You have to change the mod function.

slaur4 · Accepted Answer · 2015-02-17 13:42:41Z

As stated in the comments, it might be a variant of the Knapsack problem.

Edit : it's actually known as coin changing or change making problem.

If I understood well, you want a minimal solution to this inequation :

a₁x₁ + a₂x₂ + ... + a_nx_n >= b

The sum must be as close as possible to b with as few bills as possible.

Brute force recursive solution

Get all possible combination of bills that answer your inequation
Find the ones which sum is the closest to the solution
Find the solution using the less bills

//Available bills and money required
//var availableBills = [2, 5, 8, 16]; var money = 22;
//var availableBills = [13, 17, 30, 70, 158]; var money = 200;
var availableBills = [5, 17, 29, 70, 158];
var money = 200;
//var availableBills = [5, 10, 178]; var money = 20;
//var availableBills = [5, 20, 30, 70, 158]; var money = 157;
//var availableBills = [1, 5, 10]; var money = 97;

//Get all the money in a wallet
function getWalletSum(wallet) {
  var sum = 0;
  for (var bill in wallet) {
    sum += wallet[bill] * bill;
  }
  return sum;
}

//Copy a wallet without empty values
function copyWallet(wallet) {
  var newWallet = {};
  for (var bill in wallet) {
    if (wallet[bill] != 0) {
      newWallet[bill] = wallet[bill];
    }
  }
  return newWallet;
}

//Merge two wallets without empty values
function mergeWallets(wallet1, wallet2) {
  var mergedWallet = copyWallet(wallet1);
  for (var bill in wallet2) {
    if (wallet2[bill] != 0) {
      mergedWallet[bill] = wallet2[bill];
    }
  }
  return mergedWallet;
}

var cycles = 0;
var loops = 0;

//Get possible wallets
//Return wallets having sum >= money
function getPossibleWallets(money, startingBills) {
  cycles++;
  var possibleWallets = [];
  var wallet = {};
  var bills = startingBills.slice();
  var maxBill = bills.pop();
  wallet[maxBill] = Math.ceil(money / maxBill);
  while (wallet[maxBill] >= 0) {
    loops++;
    var walletSum = getWalletSum(wallet);
    if (walletSum == money) {
      possibleWallets.push(copyWallet(wallet));
      return possibleWallets;
    }
    if (walletSum > money) {
      possibleWallets.push(copyWallet(wallet));
    } else {
      if (bills.length > 0) {
        var remaining = money - getWalletSum(wallet);
        var remainingWallets = getPossibleWallets(remaining, bills);
        for (var i = 0; i < remainingWallets.length; i++) {
          var mergedWallet = mergeWallets(wallet, remainingWallets[i]);
          possibleWallets.push(mergedWallet);
          if (getWalletSum(mergedWallet) == money) {
            return possibleWallets;
          }
        };
      }
    }
    wallet[maxBill] = wallet[maxBill] - 1;
  }
  return possibleWallets;
}

//Get smallest possible wallet
// > Wallet sum >= money
// > Wallet sum is as close as possible to money
// > Wallet is as small as possible (less bills)
function getSmallestSufficientWallet(money, startingBills) {
  var possibleWallets = getPossibleWallets(money, startingBills);
  console.log(possibleWallets);
  var minWallet = possibleWallets[0];
  for (var i = 0; i < possibleWallets.length; i++) {
    var possibleWallet = possibleWallets[i];
    var possibleWalletSum = getWalletSum(possibleWallet);
    if (possibleWalletSum == money) {
      return possibleWallet;
    }
    if (possibleWalletSum < getWalletSum(minWallet) && possibleWalletSum >= money) {
      minWallet = possibleWallet;
    }
  }
  return minWallet;
}

var wallet = getSmallestSufficientWallet(money, availableBills);
console.log('cycles = ' + cycles);
console.log('loops = ' + loops);

//Array of bills to string
function billsToString(billsArray) {
  return billsArray.join('$, ') + '$';
}

//Wallet to string
function walletToString(wallet) {
  var result = [];
  for (bill in wallet) {
    result.push(wallet[bill] + ' * ' + bill + '$');
  }
  return result.join(' + ');
}

//Print
var questionString = '<div>Money : ' + money + '$</div>';
questionString += '<div>Available : ' + billsToString(availableBills) + '</div>';
document.getElementById('question').innerHTML = questionString;
document.getElementById('bills').innerHTML = 'Wallet : ' + walletToString(wallet);
document.getElementById('sum').innerHTML =
  '<div>Total = ' + getWalletSum(wallet) + '</div>' +
  '<div>Difference = ' + (getWalletSum(wallet) - money) + '</div>';

<div id="question"></div>
<div id="bills"></div>
<div id="sum"></div>

I don't get your comment... What do you mean by "yours don't do that" ? I have added a fiddle
The original poster expects 50 , 20 , 20 for the input 89. however, your code does not output 50, 20 , 20 , rather it outputs 50, 20 , 10 ,5 thus, you understood the question wrong.
Well, I gave a general direction to split the money, but you're right, I edited my fiddle for you...

Josep Vicent Ibanez · Accepted Answer · 2022-06-09 08:19:10Z

1

In a more compacted way:

function moneyChanger(money, bills){
    if (bills[0] < bills[1]) bills.reverse();
    const change = {};
    bills.forEach(b => {
       change[b] = Math.floor(money/b);
       money -= b*change[b];
    }) 
    return change
}

...

const change = moneyChanger(2995,[5,10,20,50,100,200,500])

The result for this example:

{5:1, 10:0, 20:2, 50:1, 100:0, 200:2, 500:5}

edited Jun 9, 2022 at 8:19

answered Oct 10, 2019 at 9:55

Josep Vicent Ibanez

1,75816 silver badges15 bronze badges

Collectives™ on Stack Overflow

Javascript Coin changing / Change making algorithm

3 Answers 3

5 Comments

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related