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>
602392714
清零编程群