Javascript换币/换币算法

Javascript Coin changing / Change making algorithm

本文关键字：算法 换币 Javascript      更新时间：2023-09-26

所以我一直在尝试用Javascript/jQuery创建一个程序，将一定数量的钱拆分成最小数量的美元钞票。到目前为止，该计划只适用于一项法案，我不太确定如何实施其余法案，需要朝着正确的方向推进。

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.";
    }
}

如果我用money = 89;运行这个，它会返回100，因为这是最接近89美元的账单，但我希望它返回50+20+20，这样它就可以用money = *anything*了。

编辑：在评论之后，我现在已经走了这么远：

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;
        }
    }
}

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));

已编辑jsfiddle

正如评论中所说，这可能是背包问题的一个变体。

编辑：这实际上被称为硬币兑换或找零问题

如果我理解得很好，你想要这个不等式的最小解：

a1x1+a2x2+…+anxn>=b

金额必须尽可能接近b，账单尽可能少。

Brute力递归解决方案

  • 获取所有可能的账单组合，以解决您的不等式
  • 找出最接近解的和
  • 使用更少的账单找到解决方案

//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>

以更紧凑的方式：

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])

这个例子的结果是：

{5:1, 10:0, 20:2, 50:1, 100:0, 200:2, 500:5}
相关文章：