Javascript cambio de moneda / cambio de algoritmo

Así que he estado intentando crear un progtwig en Javascript / jQuery que divide una cantidad de dinero en la cantidad más pequeña de billetes de dólares. Hasta ahora, el progtwig solo funciona con una sola factura, y no estoy muy seguro de cómo implementar el rest y necesito un impulso en la dirección correcta aquí.

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."; } } 

Si corro esto con money = 89; devolverá 100 porque esa es la factura más cercana que puede pagar $ 89, pero quiero que devuelva 50 + 20 + 20 para que funcione con money = *anything* .

EDIT: Después de los comentarios he llegado hasta ahora:

 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; } } } 

Como se indica en los comentarios, podría ser una variante del problema Knapsack.

Edición: en realidad se conoce como cambio de moneda o cambio de problema .

Si lo entendí bien, quieres una solución mínima a esta desigualdad:

a 1 x 1 + a 2 x 2 + … + a n x n > = b

La sum debe ser lo más cercana posible a b con la menor cantidad posible de billetes.

Solución recursiva de fuerza bruta

  • Obtén todas las combinaciones posibles de facturas que responden a tu desigualdad.
  • Encuentra las que sum es la más cercana a la solución.
  • Encuentra la solución usando menos billetes.
 //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 = '
Money : ' + money + '$
'; questionString += '
Available : ' + billsToString(availableBills) + '
'; document.getElementById('question').innerHTML = questionString; document.getElementById('bills').innerHTML = 'Wallet : ' + walletToString(wallet); document.getElementById('sum').innerHTML = '
Total = ' + getWalletSum(wallet) + '
' + '
Difference = ' + (getWalletSum(wallet) - money) + '
';
 
 var bills = [5, 10, 20, 50, 100]; var money = mod(89); function mod(num){ if (num % 5 === 0){ return num; }else{ return num + 5 - num % 5 } } function foo(num){ var index = bills.length - 1; var splits = []; while (money >= bills[0]){ if (money >= bills[index]){ money -= bills[index]; splits.push(bills[index]); }else{ index--; } } return splits; } console.log(foo(money)); 

editado jsfiddle