JavaScript硬币更改/更改算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript硬币更改/更改算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4502字，纯文字阅读大概需要7分钟。

内容图文

因此,我一直在尝试用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.";
    }
}

如果我用钱运行这个= 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;
        }
    }
}

解决方法:

如评论中所述,这可能是背包问题的一个变体.

编辑：它实际上被称为硬币更改或change making problem.

如果我了解得很好,那么您想要一个最小的解决方案：

a1x1 a2x2 … anxn> = b

总和必须与b尽可能接近,且票据越少越好.

蛮力递归解决方案

>获取所有可能解决您的不平等问题的账单组合
>找到最接近解决方案的总和
>使用更少的账单找到解决方案

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

内容总结

以上是互联网集市为您收集整理的JavaScript硬币更改/更改算法全部内容，希望文章能够帮你解决JavaScript硬币更改/更改算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端