ATM现金期权(Notes)算法

Question

我正在用Ruby开发一个ATM练习，其中一个功能是在请求现金价值之后，系统可以显示可能的现金流选项。

Ex：120雷亚尔

• 2雷亚尔$50 e 1 x雷亚尔$20
• 2雷亚尔50 e 2 x雷亚尔10美元
• 1雷亚尔100雷亚尔2雷亚尔20雷亚尔
• 6雷亚尔20美元
• 12雷亚尔10美元
• 等等。

这些纸币是有限的，也就是说，如果我在方框中只有10张纸币，那么就不会出现12x10美元的选项。

我在Java中找到了一个可能的算法，但我发现它太复杂了.

一种用有限数量的钞票给钱的ATM算法

到目前为止我的代码只是：

main.rb

# Constantes
LIMITE_SAQUE = 2000

# Variáveis
opcao = nil

saldo_atual = 5000

qtd_notas_cem = 20
qtd_notas_cinquenta = 100
qtd_notas_dez = 200
qtd_notas_vinte = 50


while opcao != 4 

# Exibe as opções do Caixa Eletrônico
puts "Qual operação você deseja?"
puts "1 - Saque"
puts "2 - Recarga de Notas"
puts "3 - Exibir Informações"
puts "4 - Sair"
puts ""

opcao = gets.to_i

case opcao
  when 1
    puts "Você escolheu a opção de Saque"
    puts "Infome o valor para saque: "
    valor = gets.to_i

    if valor <= saldo_atual && valor <= LIMITE_SAQUE
      saldo_atual = saldo_atual - valor
      puts ""
      puts "Saque efetuado no valor de R$#{valor}"
      puts "Saldo atual diponível: R$#{saldo_atual}"
      puts "" 
    elsif valor >= LIMITE_SAQUE
      puts ""
      puts "Limite de saque é superior a R$2000,00"
      puts ""
    else
      puts ""
      puts "Não existe valor dispónivel para saque."
      puts ""
    end

  when 2
    puts "Você escolheu a opção de Recarga"
    puts "Infome o valor da nota: "
    valorNota = gets.to_i

    puts "Informe agora a quantidade de notas: "
    qtdNotas = gets.to_i

  when 3
    puts "Você escolheu a opção de Informações"
  when 4
    puts "Sair..."
    %x(exit)
  else
    puts ""
    puts "!!!!!! Opçao escolhida inválida. !!!!!!"
    puts ""
  end
end

Answer 1

库存和优先级

首先，假设数组avail包含存储在机器中的每个便笺的数量。例如,

avail = [[100, 3], [50, 4], [20, 8], [10, 2], [5, 4], [1, 12]] 

此外，我们可以将此理解为提供了一个优先事项，在此基础上配发笔记。元素的这个顺序意味着应该分配尽可能多的$R100注释，最多3，然后尽可能多地分配$R50注释，最多4，等等。另一方面，如果只有在$R100注释数量不足的情况下才会配发$R50注释，则可以编写

avail = [[50, 4], [100, 3], [20, 8], [10, 2], [5, 4], [1, 12]] 

然而，在有些情况下，所有可用的注释都无法使用。例如，如果，

avail = [[50, 3], [100, 1]]

而$R200是需要的，虽然有3张，但只有2张$R50便条可以分发。

客户选择便笺组合偏好

根据客户的选择，需要从avail派生数组，我在下面称之为avail_mod。下面是一些示例(都假设可以获得有效的组合)。

1 $R100注记：

[[100, 1], [50, 4], [20, 8], [10, 2], [5, 4], [1, 12]]

3张50美元纸币：

[[50, 3], [100, 3], [20, 8], [10, 2], [5, 4], [1, 12]] 

5张$R20和2张5美元纸币：

[[20, 8], [5, 2], [100, 3], [50, 4], [10, 2], [1, 12]] 

例如，最后一个数组可以从avail派生，如下所示。

[[20, 8], [5, 2]] + avail.reject { |k,_| [20, 5].include?(k) }
  #=> [[20, 8], [5, 2], [100, 3], [50, 4], [10, 2], [1, 12]] 

应该由您来决定向客户展示的列表中有哪些可能性，以及如何针对每个选择修改avail。

代码用于计算给定客户偏好的注释组合

给定所需现金总量、amt和修改后的数组avail_mod，可以使用以下方法来确定要分发的每个钞票的数量。

def dispense(amt, avail_mod)
  (d, n), *rest = avail_mod
  if rest.empty?
    return { d=>0 } if amt.zero?
    return nil if (amt % d) > 0 || d*n < amt
    return { d=>amt/d }
  end 
  last = nil
  m = [n, amt/d].min.downto(0).find { |m| last = dispense(amt-m*d, rest) }
  m.nil? ? nil : { d=>m }.merge(last)
end

这种方法使用了一种名为动态规划的技术。它保证找到一个注释的组合，如果存在总amt，则受数组avail_mod的约束。我写它是为了优先选择更多的高面额的纸币。例如，如果需要$R588，并且avail_mod给出的$R100和$R50注释的数量分别为4和6，那么它将首先使用4个$R100注释寻找解决方案，然后使用3个$R50注释，等等。

示例

假设：

avail =     [[100, 3], [50, 4], [20, 8], [10, 2], [5, 4], [1, 12]] 
avail_mod = [[100, 2], [50, 4], [20, 8], [10, 2], [5, 4], [1, 12]

然后

spew_out = dispense(533, avail_mod)
  #=> {100=>2, 50=>4, 20=>6, 10=>1, 5=>0, 1=>3}  
spew_out.sum { |k,v| k*v }  
  #=> 533

dispense(300, avail_mod)
  #=> {100=>2, 50=>2, 20=>0, 10=>0, 5=>0, 1=>0} 

dispense(0, avail_mod)
  #=> {100=>0, 50=>0, 20=>0, 10=>0, 5=>0, 1=>0}

dispense(827, avail_mod)
  #=> nil

dispense(200, [[50,3], [100, 3]])
  #=> {50=>2, 100=>1}

avail 更新

avail.map! { |d,n| [d, n-spew_out[d]] }
  #=> [[100, 1], [50, 0], [20, 2], [10, 1], [5, 4], [1, 9]]