ATM取款算法

Question

ATM 取款算法如何工作？

从 ATM 取钱的代码应如下所示：

// 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），但不适用于您示例中的面额。

这是 change making problem 的一个变体，是一个 "hard" 问题，因为您可能必须尝试大量的组合。一种方法是至少优先考虑采用大量高价值面额的尝试，并且仅在无法找到解决方案时才尝试替代方案。

你可以这样编码：

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}

Answer 2

Javascript 中的 ATM 面额程序。

在这里，它会找到不同面额的钞票的最小数量，以求和输入的金额。从最高面额纸币到最低面额纸币开始。

检查此。这可能会帮助其他人

ATM取款算法

ATM withdrawal algorithm

javascript

algorithm

limit