Solução Informática Avançado - Semana 40

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.


// 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;
}

view raw

golfe.cpp

hosted with ❤ by GitHub