JavaScript硬币兑换零钱制作算法

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

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

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

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

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>