Otimizando a niqueleira

Sinto falta de uma nota de R$3 e de uma moeda de 15 centavos. Uma tarifa de lotação custa R$3,65 e a melhor combinação de valores é R$2+R$1+R$0,50+R$0,10+R$0,05.

Reparei que a seqüência de valores das moedas é diferente da de notas. Vou fazer de conta que a moeda de R$1 é uma nota.

Então, temos as seguintes moedas: 1, 5, 10, 25, 50. Mas as notas são 1, 2, 5, 10, 20, 50 e 100. Se existe uma combinação ótima, ela deveria ser usada nas duas seqüências, não?

Resolvi descobrir qual seqüência produz a menor contagem agregada para todos os valores entre 1 e 99. Para as moedas, seriam os valores entre 1 centavo e 99 centavos. Para as cédulas, seriam os valores entre R$1 e R$99.

my @moedas=(50,25,10,5,1);

my $total=0;
for my $valor (1..99) {
  print "\n";
  my $soma=$valor;
  print "$valor =>"; 
  for my $moeda (@moedas) {
    if($soma>=$moeda) {
      $n=int($soma/$moeda);
      $total+=$n;
      $soma-=$n*$moeda;
      print "$n*$moeda; ";
    }   
  }
}

print "\n$total\n";

O programa imprime na tela as melhores combinações para cada valor. O algoritmo é simples: ele vai da maior moeda para a menor, tentado maximimar o uso de cada uma.

Encontrei que a seqüência das notas tem uma contagem agregada de 340 (em média, são necessárias 3,43 notas) e a das moedas precisa de 420 (em média são necessárias 4,24 moedas). No entanto, a seqüência das notas tem a vantagem de ter um elemento a mais. A nota de R$2 faz toda a diferença e trocar 25 por 20 não altera em nada a contagem.

Então, sugiro que o Banco Central comece a emitir moedas de 2 centavos.

Brincando um pouco com os valores, descobri que uma nota de R$35 (ou R$30) e outra de R$15 baixariam a contagem agregada das notas para 300. Será que há uma combinação que tenha uma contagem menor que 300?