Pagini recente » Cod sursa (job #2951587) | Cod sursa (job #2259797) | Cod sursa (job #672352) | Cod sursa (job #2575974) | Cod sursa (job #1706929)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int main()
{
int n, *v, *nrmin, *pmin, S, min, aux;
f>>n>>S;
v = new int[n+1];
for(int i=1; i<=n; i++)
f>>v[i];
nrmin = new int[S+1];
pmin = new int[S+1];
nrmin[0]=0;
for(int i=1; i<=S; i++)
{
min = 100000000;
for(int j=1; j<=n; j++)
if(v[j]<=i && 1+nrmin[i-v[j]]<min)
{
min=1+nrmin[i-v[j]];
aux=j;
}
nrmin[i]=min;
pmin[i]=aux;
}
if(nrmin[S]==100000000)
g<<-1;
else
{
aux=S;
while(aux>0)
{
g<<v[pmin[aux]]<<" ";
aux=aux-v[pmin[aux]];
}
}
return 0;
}