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

一尘不染

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

algorithm

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

阅读 441

2020-07-28

共1个答案

一尘不染

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

编辑：实际上称为找零或找零问题。

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

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>

2020-07-28