A idéia básica de programação dinâmica é decompor o problema a ser resolvido em vários subproblemas, primeiro resolver os subproblemas e salvar as soluções desses subproblemas. Se você precisar usar as soluções desses subproblemas no futuro ao resolver subproblemas maiores, poderá extrair diretamente essas soluções calculadas para evitar operações repetidas. A solução para salvar subproblemas pode ser preenchida usando o método do formulário, como salvar em uma matriz.
Use um exemplo prático para refletir a idéia algorítmica de programação dinâmica - o problema da mudança de moeda.
Descrição da pergunta:
Suponha que existam várias moedas e quantidades ilimitadas. Descubra o número mínimo de moedas que podem compensar um certo número de alterações. Por exemplo, vários tipos de moedas são [1, 3, 5], o número mínimo de moedas com um valor nominal de 2 é 2 (1, 1), o número mínimo de moedas com um valor nominal de 4 é 2 (1, 3) e o número mínimo de moedas com um valor nominal de 11 é 3 (5, 5, 5, 1 ou 5, 3, 3).
Análise de problemas:
Suponha que os diferentes conjuntos de moedas sejam moedas de matriz [0, ..., n-1]. Em seguida, encontre o número mínimo de moedas com o valor face k, então a função de contagem e a moeda da matriz de moedas atendem a esta condição:
contagem (k) = min (contagem (k - moeda [0]), ..., contagem (k - moeda [n - 1])) + 1;
E a fórmula anterior apenas se mantém se a condição k - moeda [i]> = 0 && k - moeda [i] <k for atendida.
Porque k- moeda [i] <k, ao calcular a contagem (k), a contagem (i) (i <- [0, k-1]) deve ser atendida, então aqui envolve o problema do retorno.
Assim, podemos criar uma matriz matricial [k + 1] [Coin.length + 1], de modo que a matriz [0] [j] é toda inicializada em valores de 0 e salvar o número mínimo de moedas com um valor de face de i na matriz [i] [Coin.length].
E o processo específico é o seguinte:
* K | moeda 1 3 5 min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2 2, 2, 2 * ...
Finalmente, a implementação específica do código Java é a seguinte:
public static int backtrackingCoin (int [] moedas, int k) {// Método de backtracking + programação dinâmica if (moedas == null || coins.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [coins.length + 1]; for (int i = 1; i <= k; i ++) {for (int j = 0; j <coins.length; j ++) {int prek = i - moedas [j]; if (prek> -1) {// somente quando não for menor que 0, o PreK pode existir na matriz de matrizes e o backtracking pode ser executado. matriz [i] [j] = matriz [prek] [coins.length] + 1; // o valor da face i está voltando se (matrix [i] [coins.length] == 0 || matriz [i] [j] <matriz [i] [cm de moedas]) {// se o número da corrente é o número de minúsculas, o número da corrente é o número de minúsculas, o número da corrente é o número de minúsculas, o número da corrente é o número de minúsculas, o número de minúsculas é o mínimo, o número da corrente é o número da corrente, o número da corrente de minúscula é o número de minúsculas, o número de minúsculas é o mínimo, o número de minúsculas é o mínimo, o número da corrente de minúscula é o número de molhos. matriz [i] [coins.length] = matriz [i] [j]; }}} retornar matrix [k] [coins.length]; }O código foi testado e todos os casos de teste fornecidos pela pergunta foram aprovados!
Resumir
O exposto acima é o conteúdo inteiro deste artigo sobre o código de implementação do problema de mudança de moeda da programação dinâmica Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!