Javascript Изменение монеты/алгоритм изменения

Question

Итак, я пытался создать программу в 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*.

EDIT: После комментариев, которые я в настоящее время так далеко:

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

Answer 1

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

отредактировал jsfiddle

Answer 2

Как указано в комментариях, это может быть вариант задачи о рюкзаке.

Редактировать: это на самом деле известно как изменение монет или change making problem.

Если я хорошо понял, вы хотите минимальное решения этого неравенства:

а х + а х + ... + а _п х _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>