JavaScript硬币兑换/零钱制作算法

• Z时代
• 2024-01-10
• 分类：问答

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

回答：

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

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

a 1 x 1 + a 2 x 2 + … + a n x n > = 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硬币兑换/零钱制作算法 的全部内容， 来源链接： utcz.com/qa/409416.html