0.01. Recomendo utilizar - beecrowd para testar a implementação (https://judge.beecrowd.com /pt/problems/view/1021), observando que a correção automática envolve a necessidade de especificar a saída em uma formatação particular. 4. Considerando o problema do troco descrito na questão anterior, responda: a. Como poderíamos resolver problema usando programação dinâmica e por que essa abordagem é menos efficiente (exponencial ou pseudopolinomial)? b. Por que a abordagem gulosa pode não ser ótima em todos os cenários desse problema? Imagine por exemplo, o troco de 30 reais e que as notas disponíveis são de 50,25,10 e 1 reais.

Question

0.01. Recomendo utilizar - beecrowd para testar a implementação (https://judge.beecrowd.com /pt/problems/view/1021), observando que a correção automática envolve a necessidade de especificar a saída em uma formatação particular. 4. Considerando o problema do troco descrito na questão anterior, responda: a. Como poderíamos resolver problema usando programação dinâmica e por que essa abordagem é menos efficiente (exponencial ou pseudopolinomial)? b. Por que a abordagem gulosa pode não ser ótima em todos os cenários desse problema? Imagine por exemplo, o troco de 30 reais e que as notas disponíveis são de 50,25,10 e 1 reais.

Answer 1

Vamos detalhar um pouco mais as respostas para garantir que tudo esteja claro.### a. Programação Dinâmica**Como resolver usando programação dinâmica:**1. **Defina a matriz DP:** Crie uma matriz DP onde DP[i][j] representa o número mínimo de notas de valor i que são necessárias para formar um valor j.2. **Inicialize a matriz DP:** - DP[0][j] = 0 para todos os j, pois zero notas são necessárias para formar zero. - Para j > 0, inicialize DP[i][0] = ∞ para todos os i > 0, pois não é possível formar um valor zero usando notas de valor positivo.3. **Preencha a matriz DP:** Para cada i e j, considere todas as notas disponíveis (50, 25, 10, 1) e atualize DP[i][j] com o mínimo entre DP[i][j] e DP[i-50][j-50] + 1, DP[i-25][j-25] + 1, DP[i-10][j-10] + 1, DP[i-1][j-1] + 1.4. **Obtenha o resultado:** O valor mínimo em DP[N][T] será o número mínimo de notas necessárias para formar o troco T.**Por que essa abordagem é menos eficiente:**- **Complexidade Exponencial:** Cada célula DP[i][j] depende de todas as células DP[i-50][j-50], DP[i-25][j-25], DP[i-10][j-10] e DP[i-1][j-1]. Isso resulta em uma complexidade de O(T * N), onde T é o valor do troco e N é o número de notas disponíveis.- **Espaço Exponencial:** A matriz DP terá tamanho N x T, o que também contribui para o aumento do espaço necessário.### b. Abordagem Gulosa**Por que a abordagem gulosa pode não ser ótima:**- **Exemplo de falha:** Considere o troco de 30 reais e as notas disponíveis (50, 25, 10, 1). A abordagem gulosa sempre escolherá a nota maior possível para cada passo. No entanto, isso pode levar a um número maior de notas do que necessário. Por exemplo, em vez de usar uma nota de 25 reais para formar 30 reais, você poderia usar uma nota de 10 reais e uma nota de 10 reais, resultando em um número menor de notas.**Exemplo concreto:**- **Troco de 30 reais:** - Abordagem gulosa: 1 nota de 25 reais + 1 nota de 5 reais = 2 notas. - Abordagem ótima: 1 nota de 10 reais + 1 nota de 10 reais + 1 nota de 5 reais + 1 nota de 5 reais = 4 notas.Portanto, a abordagem gulosa pode não ser a mais eficiente ou ótima, pois pode levar a soluções subótimas em alguns casos.

Question

Solution

Resposta