[RESOLVIDO] Problema com moedas de valores diversos

Programação Java
#1

E aí pessoal! Queria uma opinião da galera mais ligada na matemática aqui :sweat_smile:
Tenho o seguinte problema: meu programa deve receber um vetor com 1 a 10 posições, onde cada uma representa o valor de uma moeda, ou nota de um sistema monetário qualquer. Pode ser qualquer valor, e é aí que está o problema…
Preciso testar quantos e quais valores entre 1 e 10000 que não poderão ser pagos com esse sistema monetário, utilizando as moedas necessárias para formar um valor. É parecido com o problema do caixa eletrônico, com a diferença que muitas vezes não será possível pagar algum valor. Eu tenho o código abaixo, o problema é que ele deixa passar alguns valores, como se eles não pudessem ser pagos. O problema é que não consigo pensar em outra forma boa e eficiente de resolver o problema, e sendo uma atividade da cadeira de complexidade de algoritmos, precisa ser um programa rápido, levando menos de um minuto pra rodar.
’’'
import java.sql.Date;
import java.text.SimpleDateFormat;

public class QuartoDesafioFinal {

private static int valoresDeMoedas[] = {5, 11, 13};
private static int valoresAPagar = 10000;
private static int numerosATestar[] = new int[valoresAPagar];

public static void main(String[] args) {

    //processo de ordenação do vetor de moedas
    //valoresDeMoedas = quickSort(valoresDeMoedas, 0, valoresDeMoedas.length - 1);

    int numerosImpossiveis[] = new int[valoresAPagar];
    int valorSobra;
    int indice;
    int j = 0;
    int valorInicial;

    long inicio = System.currentTimeMillis();

    for (int n = 0; n < numerosATestar.length; n++) {
        numerosATestar[n] = n + 1;
    }

    for (int aNumerosATestar : numerosATestar) {
        valorSobra = aNumerosATestar;
        valorInicial = valorSobra;
        indice = valoresDeMoedas.length - 1;
        while (indice >= 0) {
            if (valorSobra >= valoresDeMoedas[indice]) {
                valorSobra -= valoresDeMoedas[indice];
            } else {
                indice--;
            }
        }
        if (valorSobra > 0) {
            numerosImpossiveis[j] = valorInicial;
            j++;
        }
    }

    System.out.println("Quantidade de números impossíveis de pagar: " + (j) + "\n");
    System.out.println("Os seguintes números não poderão ser pagos com a moeda da Teluria:");

    for (int numerosImpossivei : numerosImpossiveis) {
        if (numerosImpossivei > 0) {
            System.out.println(numerosImpossivei);
        }
    }

    long fim = System.currentTimeMillis();
    System.out.println("\nTempo decorrido:");
    System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));
}

‘’’

#2

No construtor da classe SistemaMonetario, você passa um array de Long com as moedas disponíveis. Essa técnica se chama memoization, e é uma forma de eliminar cálculos repetidos em problemas de programação dinâmica.

A complexidade desse algoritmo é O(n) por causa da memoization.

Detalhe: o compilador do java não consegue fazer tail call optimization nesse caso de recursão. Por isso, dependendo do tamanho do número que você passar, pode dar Stack Overflow. Existe uma forma de permitir essa otimização. Consegue pensar nela?

Se você fizer só essa chamada, por exemplo, no main, vai causar StackOverflow:

System.out.println(String.format("Consegue pagar %d? %b", 100000l, sm.conseguePagar(100000l)));

import java.util.HashMap;

class SistemaMonetario {

    private final HashMap<Long, Boolean> conseguePagarMemo;
    private final Long[] moedas;

    SistemaMonetario (Long[] moedas) {
        this.moedas = moedas;
        this.conseguePagarMemo = new HashMap<>();
    }

    private boolean calcularResultadoPara(Long quantia, int indice) {
        if (quantia == 0)
            return true;
        if (indice >= moedas.length || quantia < 0)
            return false;
        Boolean memo = conseguePagarMemo.get(quantia);
        if (memo != null)
            return memo;

        boolean resultado = calcularResultadoPara(quantia - moedas[indice], indice) || calcularResultadoPara(quantia, indice + 1);
        conseguePagarMemo.put(quantia, resultado);
        return resultado;
    }

    boolean conseguePagar(Long quantia) {
        return calcularResultadoPara(quantia, 0);
    }

}

public class Main {

    public static void main (String[] args) {
        Long[] moedas = {2l, 5l, 10l, 20l, 50l, 100l};
        SistemaMonetario sm = new SistemaMonetario(moedas);
        for (long i = 0l; i <= 100l; i++)
            System.out.println(String.format("Consegue pagar %d? %b", i, sm.conseguePagar(i)));
    }
}
#3

Cara, resolveu meu problema! É incrível a quantidade de números que se consegue pagar apenas com essas moedas do meu exemplo. Funcionou perfeitamente, agora vou fazer um debug detalhado do meu programa pra estudar essa técnica e usar no futuro. Valeu cara!