Solução por Matheus, comentário de João Guilherme
Temos uma questão de dp simples. A dp representa o menor número de blocos necessários para alcansar o tamanho olhado, o único estado é o tamanho que estamos olhando, e a passagem é checar para cada tamanho de bloco se é possível alcansar o estado com o tamanho que estamos analisando menos o bloco olhado, e se for tomar o mínimo.
Segue código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <cstring> | |
| #include <algorithm> | |
| #define INF 999999999 | |
| using namespace std; | |
| int dp [1000500]; | |
| int main() | |
| { | |
| int T; | |
| scanf("%d", &T); | |
| for(int z = 0; z< T; z++) { | |
| int coin[100], val, n, i, j; | |
| memset(dp, 0, sizeof(dp)); | |
| scanf("%d%d", &n, &val); | |
| for(int i =1;i<=n;i++) | |
| scanf("%d", &coin[i]); | |
| dp[0] = 0; | |
| for(i=1;i<=val;i++) dp[i] = INF; | |
| for(i=1;i<=val;i++) | |
| { | |
| for(j=1;j<=n;j++) | |
| { | |
| if(i - coin[j]>=0) | |
| { | |
| dp[i] = min(dp[i], dp[i-coin[j]] + 1); | |
| } | |
| } | |
| } | |
| printf("%d\n", dp[val]); | |
| } | |
| return 0; | |
| } |