ATM提款算法

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

...but结果不正确：

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的一种变体，是一个“难”的问题，因为您可能需要尝试大量的组合。一种方法是至少优先考虑采用许多较高价值面值的尝试，只有在这些尝试不能导致解决方案时才尝试替代方案。

你可以像这样编写代码：

​

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编写的自动柜员机计价程序。

在这里，它将找到不同面额的纸币的最小数量，它们的总和为输入的金额。从最高面额的纸币到最低面额的纸币。

检查此https://stackoverflow.com/a/66456375/9248245。这可能会帮助其他人。