Esse é outro problema de programação dinâmica, uma variação do problema clássico do troco, sendo que nesse caso queremos mínimizar o número de moedas (ou nesse problema, tacadas).
Para esse problema vamos considerar a $$dp_i$$, a quantidade mínima de tacadas para chegar no valor $$i$$, $$inf$$ caso seja impossível.
Temos a seguinte recurção:
- Caso $$i = 0$$, caso base $$dp_i = 0$$
- Caso $$i < 0$$, caso em que é impossível chegar a 0, $$dp_i = inf$$
- Caso $$i > 0$$, podemos colocar qualquer moedas, então $$dp_i = \min\limits_{i=1}\limits^n(dp_{i-c_i} + 1)$$
A partir disso fazemos a recursão partindo da distância máxima, para achar o mínimo de tacadas partindo do $$0$$, caso impossível podemos calcular uma dp semelhate a acima ou podemos somente ver se $$dp_m = inf$.
Código para melhor entendimento:
OBS: O código enviado esqueceu de fazer a memorização na dp que achava o mínimo, então corrigi isso.
This file contains hidden or 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
| // solucao por Bruno Mello | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int N=100002; | |
| const int inf=0x3f3f3f3f; | |
| int v[N]; | |
| int n,d; | |
| int dp[N], u[N], dp2[N]; | |
| bool possivel(int d){ | |
| if(d==0)return 1; | |
| if(d<0)return 0; | |
| if(dp[d]>=0)return dp[d]; | |
| for (int i=1;i<=n;i++){ | |
| if(possivel(d-v[i])==1) return dp[d]=1; | |
| } | |
| return dp[d]=0; | |
| } | |
| int solve(int d){ | |
| if(d==0)return 0; | |
| if(d<0)return inf; | |
| if(dp2[d] >= 0) return dp2[d] | |
| int menor=inf; | |
| for (int i=1;i<=n;i++){ | |
| menor=min(menor,solve(d-v[i])); | |
| } | |
| return dp2[d] = menor+1; | |
| } | |
| int main() | |
| { | |
| cin >> n >> d; | |
| memset(dp,-1,sizeof(dp)); | |
| memset(dp2, -1, sizeof(dp2)); | |
| for (int i=1;i<=n;i++){ | |
| scanf("%d", &v[i]); | |
| } | |
| if(possivel(d)==0){ | |
| printf("-1\n"); | |
| return 0; | |
| } | |
| printf("%d\n", solve(d)); | |
| return 0; | |
| } |