алгоритм снятия наличных в javascript

Question

Как работает алгоритм снятия средств банкомата?

Мне нужно получить деньги в банкомате, если он доступен с кодом, подобным этому:

// count of nominals in ATM
let limits = {
  1000: 5,
  500: 2,
  100: 5,
  50: 100,
  30: 6
}

let getMoney = (amount, limits) => {
  ...
};

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {} | i need {100: 2, 30: 1}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 3} | i need {100: 1, 50: 1}
console.log(getMoney(120, limits)); // {30: 4}

Я пытаюсь сделать это:

let getMoney = (am, lm) => {
  Object.keys(lm).map( k => {
    if(lm[k] && am / k >= 1 && am % k === 0)
      if(lm[k] > am / k)
        r[k] = am / k;
  });
};

, но результат неверный:

console.log( getMoney(1000, limits) ); // {1000: 1}
console.log( getMoney(230, limits) ); // {} | i need {100: 2, 30: 1}
console.log( getMoney(200, limits) ); // {100: 2}
console.log( getMoney(150, limits) ); // {50: 3} | i need {100: 1, 50: 1}
console.log( getMoney(120, limits) ); // {30: 4}

Answer 1

Ваш алгоритм предполагает, что, если есть решение, тогда это решение будет использовать большую часть наивысшего доступного номинала, которая все еще соответствует оставшейся сумме.Это будет работать для некоторых наборов конфессий, таких как общий (1000, 500, 200, 100, 50, 20, 10, 5, 2, 1), но не для одного в вашем примере.

Это вариант проблемы внесения изменений и является "сложной" проблемой, в которой вы потенциально должны попробовать огромное количество комбинаций.Одним из способов является, по крайней мере, отдавать приоритет попыткам, которые принимают большую часть более ценных достоинств, и пробовать альтернативы только тогда, когда они не приводят к решению.

Вы можете написать код следующим образом:

let getMoney = (amount, limits) => {
    let recur = (amount, nominals) => {
        if (amount == 0) return {}; // success
        if (!nominals.length) return; // failure
        let nominal = nominals[0];
        let count = Math.min(limits[nominal], Math.floor(amount / nominal));
        for (let i = count; i >= 0; i--) {
            let result = recur(amount - i*nominal, nominals.slice(1));
            if (result) return i ? { [nominal]: i, ...result } : result;
        }
    }
    return recur(amount, Object.keys(limits).map(Number).sort((a,b) => b - a));
};

// count of nominals in ATM
let limits = { 1000: 5, 500: 2, 100: 5, 50: 100, 30: 6 }

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {30: 1, 100: 2}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 1, 100: 1}
console.log(getMoney(120, limits)); // {30: 4}