如评论中所述，这可能是背包问题的一个变体。
编辑：实际上称为找零或 找零问题。
如果我了解得很好，那么您需要一个最小的解决方案：
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>
