BastterCode Monthly Maio - 322. Coin Change
comentada em 01/06/2023 16:30

Se entendi bem, acho que seria isto, em Go:

func MinCoins(coins []int, ammount int) int {

	// Não está especificado se o array de moedas é ordenado, se 
	// for isto não seria necessario. Alem disto, o array 
	// aqui é modificado in-place.
	sort(coins)

	var min int

	for i := len(coins)-1; i >= 0; i-- { 
		c := coins[i]
		min = min + ammount / c
		ammount = ammount % c
	}

	if ammount > 0 { 
		return -1
	}

	return min
}

// Esta é uma implementação pobre de ordenação, mas 
// o numero de objetos é limitado a 12 pela spec.
func sort(coins []int) { 

	for i:=0; i < len(coins) - 1; i++ { 
		for j:=i+1; j < len(coins) - 1; j++ { 
			if coins[i] > coins[j] { 
				c := coins[j]
				coins[j] = coins[i]
				coins[i] = c
			}
		}
	}

}
?

@gummybear testou lá no link ?

Eita @FlyCavok, nao sabia que tinha como testar lá e nem tenho conta na verdade. Perdoe-me não vi as regras do desafio, achei que era so algo interno aqui da Bastter mesmo, para se divertir... :^)

De qualquer modo fui dar uma olhada e vi que não aceitam Go, vou converter para C++ e se criar uma conta não for algo muito chato posto la.

Eu "testei" com isto aqui:

func main() { 

	c:=[]int{1, 4, 5, 2, 10} 
	sort(c)
	fmt.Printf("%v
", c)

	fmt.Printf("1-5: %d
", MinCoins([]int{1, 2, 3, 4, 5}, 11)) 
	fmt.Printf("1-5: %d
", MinCoins([]int{3, 1, 2, 5, 4}, 11)) 
	fmt.Printf("1-2: %d
", MinCoins([]int{1, 2}, 11)) 
	fmt.Printf("c(1,2,5)a(11): %d
", MinCoins([]int{1, 2, 5}, 11)) 
	fmt.Printf("1-3: %d
", MinCoins([]int{1, 2, 3}, 11)) 
	fmt.Printf("c(2)a(3): %d
", MinCoins([]int{2}, 3)) 
	fmt.Printf("c(1)a(0): %d
", MinCoins([]int{1}, 0)) 

}
?

Não deu, falha para:


coins = [186,419,83,408]


amount =6249

Tive um bocado de trabalho nessa daqui, ontem fiz uma versão recursiva e hoje fiz uma versão iterativa.

Antigamente o Giovanni pedia para a gente colocar comentários no código explicando o raciocínio para ajudar outras pessoas que estiverem estudando. Mas toda vez fica mal formatado, então eu venho escrevendo os comentários aqui no corpo do tópico mesmo.

Dessa vez, considerando que esse assunto é meio chatinho, eu vou detalhar o meu processo mental até chegar na resposta, que aí me ajuda quando eu tiver reestudando no futuro e pode ajudar também alguém que esteja empacado.

A questão é sobre programação dinâmica. Eu coloquei uma aula bem completa lá no desafio semanal pra quem quiser assistir.

Em resumo, programação dinâmica é uma técnica para resolver problemas que tem uma estrutura tal que para resolver para um valor X, você precisa resolver para um valor X - Y e a resolução segue a mesma lógica tanto para X quanto para X - Y. E esse comportamento segue sucessivamente, para X - Y - Z, X - Y - Z - L, assim por diante até chegar a um resultado base que é dado.

Nesse tipo de situação, você pode simplesmente salvar o cálculo feito para um valor menor e reaproveitar quando tiver calculando para o valor maior, evitando o recálculo e reduzindo bastante a complexidade computacional.

Basicamente é essa a técnica, você primeiro verifica se já tem a resposta salva, se não tiver você calcula e salva e assim por diante até chegar ao resultado desejado.

Devido a essa estrutura, geralmente é mais intuitivo resolver problemas de programação dinâmica com recursão, ou seja, com a função que calcula X chamando a si mesma para calcular X - Y, que por sua vez chama a si mesma para calcular X - Y - Z, assim por diante até chegar ao valor base dado.

Algo mais ou menos assim:

Estrutura_de_dados Resultados
Função (parâmetro X) {
   if (Resultados[X]) retorna Resultados[X]
   if (X == Parâmetro_Base) {
      Resultados[X] = Valor_Base
      retorna Resultados[X]
   }

   retorna Função(X-Y) + Diferença;
}?

A questão aí do desafio é a seguinte.

Você tem um conjunto de moedas, que podem ser combinadas para resultar diferentes valores. Eu quero saber o menor número de moedas necessárias para gerar um montante pedido.

Os parâmetros base são as moedas. Se o montante pedido for igual a qualquer moeda, então o número de moedas necessárias será 1 (basta a moeda em questão para chegar ao montante). Então o valor base, para cada moeda informada, é 1.

Além disso, para calcular o resultado para um montante maior, eu uso o resultado dos montantes menores.

Por exemplo, se minhas moedas são 2, 3 e 7 e o montante for 13.

Se eu pego uma moeda dentre as que eu tenho, para chegar a 13 ficam faltando 11 (se a moeda foi 2), 10 (se a moeda foi 3) ou 6 (se a moeda foi 7).

O número mínimo de moedas para pagar 13 é, portanto, igual ao menor número dentre o número mínimo de moedas para pagar 11, 10 ou 6, mais a moeda adicional que eu peguei.

Por exemplo, se eu preciso de 4 moedas para pagar 11, 3 para pagar 10 e 2 para pagar 6, então eu consigo pagar 13 usando as 2 para pagar 6 e mais 1 moeda de 7, completando 3 moedas ao todo.

Logo, para resolver a questão usando recursão, eu vou fazer o seguinte:

1- criar uma estrutura de dados que vai salvar o número de moedas necessários para cada valor, evitando o recálculo;
2- preencher essa estrutura de dados com os parâmetros base, que são as moedas do vetor coins. O valor para cada moeda será 1, pois se o montante for igual à moeda, bastará 1 moeda para pagar o montante;
3- calcular função para montante - cada moeda e verificar o menor resultado. Esse é o menor número de moedas necessário para pagar montante - cada moeda;
4- a função vai chamando a si mesma para montantes cada vez menores até chegar ao parâmetro base. Aí ela já tem o resultado armazenado na estrutura de dados e pega lá. Uma vez feito esse cálculo, ele vai ser armazenado também na estrutura de dados para ser aproveitado toda vez que eu precisar desse resultado novamente;
5- daí a função vai passando valores sucessivamente, de trás pra frente, até que eu consiga a resposta que eu quero.

Além disso, eu preciso atentar para as situações que fogem ao esperado:

6- se o montante for 0, a função deve retornar 0, independente das moedas;
7- se as moedas disponíveis não conseguirem resultar no montante esperado em qualquer combinação, a função deve retornar -1;

Enfim, depois de toda essa explicação gigante, segue o código que eu fiz com recursão. É um código de iniciante, certamente tem muito espaço pra otimização.

class Solution {
public:
    vector<int> num_coins{};
    
    int coinChange(vector<int>& coins, int amount) {
        num_coins.resize(10001);
        
        if (amount == 0 || num_coins[amount]) return num_coins[amount];
        
        bool all_coins_greater = true;
        int minimum_coins = 10000;
         
        for (int i = 0; i < coins.size(); ++i) {
            int coin_value = coins[i];
            
            if (amount == coin_value) {
                num_coins[amount] = 1;
                return 1;
            } else if (coin_value <= 10000 && num_coins[coin_value] == 0) num_coins[coin_value] = 1;            
            
            if (coin_value < amount) {                
                int num_of_coins_dif = coinChange(coins, amount - coin_value);
                
                if (num_of_coins_dif != -1) {
                    all_coins_greater = false;
                    if (num_of_coins_dif + 1 < minimum_coins) minimum_coins = num_of_coins_dif + 1;
                }
            }
        }
        
        if (all_coins_greater) num_coins[amount] = -1;
        else num_coins[amount] = minimum_coins;
                                                                                                     
        return num_coins[amount];
    }
};

A estrutura de dados que armazena os valores é o vetor num_coins, que precisa ser criado fora da função, de maneira "global", para que seus valores possam ser utilizados em chamadas diferentes da mesma função.

Logo no início da função, é feita a verificação se já existe valor armazenado no vetor para o montante informado. Se já existir, a função retorna logo o valor e evitar o recálculo. Na mesma verificação, já é tratada a hipótese do montante = 0, que retornará 0 independente das moedas.

Existe uma variável booleana chamada all_coins_greater, cuja função é verificar se, quando a função for chamada para um determinado montante, existe alguma combinação de moedas que gere esse montante. Se não existir, a função vai retornar -1.

Existe uma variável inteira chamada minimum_coins, cuja função é permitir a comparação do número de moedas de diferentes combinações para um mesmo montante, de maneira a identificar o menor número de moedas, que é a resposta buscada.

Em seguida, há um loop que percorre as moedas.

Nele, primeiro se insere no vetor o valor base de 1 para cada moeda que seja menor a 10000. A razão dessa limitação é que nas restrições da questão consta que o montante máximo é 10000, enquanto as moedas podem ser bem maiores que isso. Então não é preciso armazenar valores que são superiores ao maior montante possível.

Depois, se o valor da moeda for inferior ao montante, é feita uma chamada recursiva à função para montante - valor da moeda. Isso só é feito para moedas menores que o montante, pois as maiores jamais poderão participar de uma combinação que gere o montante.

Se a chamada recursiva der valor diferente de -1, então all_coins_greater é falsa. Isso significa que existe pelo menos uma combinação possível para aquele montante, pois existe uma combinação possível para montante - moeda e disso para montante basta acrescentar uma moeda, o que é sempre possível. Se a chamada retornasse -1, significaria que não existe combinação para montante - moeda.

Além disso, se a chamada der diferente de -1, a chamada vai representar o menor número de moedas para pagar montante - moeda. O menor número entre diferentes valores de montante - moeda (que depende da moeda, que saberemos conforme o loop percorra todas elas) será passado para minimum_coins, somado a 1. Esse 1 adicional é a moeda extra que eu preciso usar para chegar a montante.

Finalmente, se all_coins_greater for positivo, isso significa que não houve combinação possível para aquele montante, então a função retorna -1. Do contrário, eu armazeno no meu vetor para montante o valor correspondente a minimum_coins e então retorno esse valor na função.

Como esperado, o código não é o mais eficiente, mas rodou razoavelmente bem:

Ver mais

Ali em cima foi a versão recursiva, agora vou colocar uma com iteração.

Eu comecei a explicar o raciocínio, mas acabou que não deu tempo. Quando sobrar tempo, eu explico. O desempenho dessa versão foi bem melhor, mas o consumo de memória ainda tá ruim.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        
        vector<int> results{};
        vector<int> num_coins(amount + 1);
        
        int count = 1;
        bool all_values_greater = true;
        
        for (int i = coins.size() - 1; i >= 0; --i) {
            if (coins[i] == amount) return 1;
            if (coins[i] < amount) {
                results.push_back(amount - coins[i]);
                num_coins[coins[i]] = count;
                all_values_greater = false;
            }
        }
        
        while (all_values_greater == false) {
            vector<int> temp{};
            int answer = INT_MAX;
            
            all_values_greater = true;
            count++;
            
            for (int i = coins.size() - 1; i >= 0; --i) {
                for (int p = results.size() - 1; p >= 0; --p) {
                    int dif = results[p] - coins[i];
                    if (dif == 0) return count;
                    if (dif > 0) {
                        if (num_coins[dif]) {
                            if (count + num_coins[dif] < answer) answer = count + num_coins[dif];
                        }
                        if (num_coins[amount - dif] == 0) {
                            temp.push_back(dif);
                            num_coins[amount - dif] = count;
                        }
                    }
                }
            }
            
            if (answer != INT_MAX) return answer;
            
            if (temp.size() != 0) {
                all_values_greater = false;
                results = temp;
            }
        }        
        return -1;
    }
};?

@gummybear isso o ideal lá do site é que ele tem testes unitários pro código. Então o ideal é testar lá. 
Se você quiser, pode pedir ao chat gpt pra converter teu código.
Em geral ele é bom nisso. Se for pra outra linguagem que vc conhece, da pra bater o olho e ver se ele não escreveu bobagens hehehe

Acredito que você deva programar em várias linguagens. Ninguém escolhe Go como primeira linguagem, pelo menos nunca vi.

@gummybear

O leetcode aceita Go sim, olha:

Minha solução em C#

btChange implementa o algoritmo e retorna o custo mínimo para o par i, amount,  onde i representa a moeda que eu estou olhando no momento e amount o total pretendido a ser alcançado. As regras são:

se i > máximo de moedas, retorno um valor elevado para ser ignorado.

se amount == 0, é pq já atingi o objetivo, tem que retornar zero, pois não há mais custo

se amount < 0 é pq não é possível atingir o objetivo, retorno um valor alto para ser ignorado.

caso contrário, olho no cache se tem solução para i, amount.  Se não tiver, computo fazendo:

minimo ( usar a moeda atual mais uma vez, passar para a próxima moeda)

public class Solution {
    
    private int [] coins;
    private int [,] cache;
    
    
    private int btChange(int i, int amount) {
        
        if (i >= coins.Length) {
            return int.MaxValue - 1;
        }
        
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return int.MaxValue - 1;
        }
        
        if (cache[i, amount] == -1) {
            cache[i, amount] =  Math.Min(btChange(i, amount - coins[i]) + 1, btChange(i+1, amount));
        }
        
        return cache[i, amount];
    }
    
    
    public int CoinChange(int[] coins, int amount) {
        this.coins = coins;
        this.cache = new int [coins.Length+1, amount+1];
        
        for (int i = 0; i <= coins.Length; i++)
            for (int j = 0; j <= amount; j++)
                cache[i,j] = -1;
        
        
        int p =  btChange(0, amount);
        if (p == int.MaxValue - 1) return -1;
        return p;
    }
}?

Vou colocar isso aqui também, só porque acho que é mais fácil de achar depois num desafio mensal que num semanal.

Aula do freeCodeCamp sobre programação dinâmica. É uma aula longa, de 5h, que cobre o assunto bem explicadinho desde o começo, com vários exemplos:



Série de aulas da cadeira de Introdução aos Algoritmos, do MIT, gravadas na Primavera de 2020. A parte de programação dinâmica começa na aula 15:

Deixando aqui outra referência que apareceu p mim no Twitter

este vídeo é de um Eng de Software da Meta explicando uma das técnicas p resolver problemas de Prog Dinâmica - Memoization

Dei uma organizada na minha versão recursiva:

1- criando um método para inicializar o vetor uma única vez, evitando chamadas desnecessárias para o resize();
2- eliminando um booleano cuja informação já poderia ser obtida através da variável que descobre o menor número de moedas para chegar a um número (se essa variável mudou de valor, então existe alguma combinação que chega no número, não preciso de outra variável para armazenar essa informação);
3- retirando alguns condicionais que se tornam obsoletos se a recursão chegar ao 0 ou se a variável que descobre o menor número de moedas sair do loop; e
4- usando iterador para percorrer o vetor de moedas.

Impressionante que só com isso o consumo de memória nos testes do leetcode consistentemente caiu de uma média de 20 MB para uma de 15 MB. Uma redução de 25%!

class Solution {
public:
    vector<int> number_of_coins{};
    
    void resizeVector(int size) {
      number_of_coins.resize(size);
    }
    
    int coinChange(vector<int>& coins, int amount) {
      if (number_of_coins.size() == 0) resizeVector(amount + 1);
        
      if (number_of_coins[amount] || amount == 0) {
        return number_of_coins[amount];
      }
        
      int change = 10001;
        
      for (::vector<int>::iterator i = coins.begin(); i != coins.end(); ++i)         
      {
        if (*i <= amount) {
            if (coinChange(coins, amount - *i) != -1) {
                change = min(change, coinChange(coins, amount - *i) + 1);
            }               
        }
      }
        
      if (change == 10001) number_of_coins[amount] = -1;
      else number_of_coins[amount] = change;
        
      return number_of_coins[amount];
  }
};?

Alô @oxe, na primeira vez que entrei não percebi, mas de fato. Tks!

Agora que o mês acabou, fui lá no site conferir as melhores respostas para C++.

Essa aqui teve um consumo de tempo similar à da minha versão iterada, só que gastando menos memória e com um código evidentemente muito mais simples, legível e enxuto:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount<1) return 0;
        int i;
        vector<int> ans(amount+1, INT_MAX);
        ans[0] = 0;
        
        for (int coin: coins) {
            for (int i=coin; i<=amount; i++) {
                if (ans[i-coin]!=INT_MAX)
                    ans[i] = min(ans[i], 1 + ans[i-coin]);
            }
        }
        
        return ans[amount] == INT_MAX ? -1: ans[amount];
    }
};?

Essa aqui gastou apenas metade do tempo da minha versão iterada e também gastou metade da memória:

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount)
	{
        int dp[amount + 1];
        dp[0] = 0;

		// O(coins * log(coins))
        std::sort(begin(coins), end(coins));

        for (int a = 1; a <= amount; a++)
        {
            dp[a] = INT_MAX;
            for (int c: coins)
            {
                if (a - c < 0)
                    break;
                else if (dp[a - c] != INT_MAX)
                    dp[a] = std::min(dp[a], 1 + dp[a - c]);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};?

Os dois códigos têm uma abordagem muito parecida, talvez tenha sido inclusive a mesma pessoa que postou o primeiro e depois foi melhorando até chegar ao segundo.

A diferença entre ambas é:

1- no primeiro ele usa um vetor, que é um array dinâmico. Já no segundo ele usa um array fixo para rastrear os resultados das moedas, o que é possível já que o número possível de resultados é sempre inferior ao montante informado inicialmente;

2- no segundo ele faz um sort das moedas em ordem crescente, o que permite incluir uma condicional para quebrar o loop quando a moeda for maior que o resultado rastreado;

A lógica do algoritmo do segundo programa (que é quase igual ao do primeiro) é a seguinte:

Ele usa um array de rastreio. Depois ele vai conferir, para cada valor abaixo ou igual ao montante informado, se a diferença entre o valor e cada uma das moedas é diferente do valor padrão de inicialização, que ele setou como 0 para o índice 0 e como INT_MAX para o resto.

Como os resultados são testados em ordem crescente, o valor de inicialização da diferença vai ser diferente de INT_MAX sempre que houver alguma combinação de moedas que gere aquele resultado.

Porque, se existe uma moeda igual ao resultado, a diferença é 0, cujo valor de inicialização é setado em 0. Se não houver uma moeda igual ao resultado, então a única forma de chegar ao resultado é através da combinação de mais de uma moeda, de forma que a diferença entre o resultado e uma das moedas é igual à soma das demais moedas combinadas.

Como o índice dessa diferença entre o resultado e uma das moedas é menor que o índice do resultado (já que tanto o resultado como todas as moedas são inteiros positivos), então o programa já teria preenchido o array para o índice correspondente à diferença antes de preencher para o índice correspondente ao resultado.

Logo, o valor para o índice correspondente à diferença será diferente de INT_MAX se houver uma combinação de moedas que gere essa diferença.

Além disso, como as moedas foram ordenadas de forma crescente, então se a diferença entre o resultado e a moeda analisada for menor que 0, então o loop pode ser quebrado, já que nem a moeda atual, nem as seguintes (que são maiores que a atual), podem compor uma combinação que gere o resultado desejado.

O legal é que essa quebra do loop é mais eficiente que apenas descartar as moedas maiores que o montante, pois ela vale para todos os valores menores que o montante. Por exemplo, se o montante é 13 e eu estou preenchendo bottom-up o número de moedas que geram todos os resultados antes de 13, então eu não preciso considerar a moeda 7 para o resultado 5, mas eu precisaria considerar a moeda 7 para o resultado 7 em diante.

Enfim, muito legal. Aprendi bastante.