gde gresim
#include<iostream>
using namespace std;
int main()
{int n,k;
cin>>n;
cin>>k;
int c[n+1];
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
for(int i=1;i<=n-1;i++)
{
int ind=i;
for(int j=i+1;j<=n;j++)
if(c[ind]>c[j])
ind=j;
if(ind!=i)
{
int pom=c[ind];
c[ind]=c[i];
c[i]=pom;
}
}
int v[k+1];
v[0]=0;
int b[k+1];
b[0]=0;
for(int i=1;i<=k;i++)
{ b[i]=0;
v[i]=k;
for(int j=1;j<=n;j++)
{
if(i<c[j])continue;
if(v[i-c[j]]+1<v[i])
v[i]=v[i-c[j]]+1;
b[i]=j;
}
}
int s=0;
int p=k;
while (b[p]>0)
{
s+=c[b[p]];
p-=c[b[p]];
}
if(s==k)
cout<<v[k];
else cout<<"-1";
}
prolazi 12 primera
vreme nije problem
#include<iostream>
using namespace std;
int main()
{int n,k;
cin>>n;
cin>>k;
int c[n+1];
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
for(int i=1;i<=n-1;i++)
{
int ind=i;
for(int j=i+1;j<=n;j++)
if(c[ind]>c[j])
ind=j;
if(ind!=i)
{
int pom=c[ind];
c[ind]=c[i];
c[i]=pom;
}
}
int v[k+1];
v[0]=0;
int b[k+1];
b[0]=0;
for(int i=1;i<=k;i++)
{ b[i]=0;
v[i]=k;
for(int j=1;j<=n;j++)
{
if(i<c[j])continue;
if(v[i-c[j]]+1<v[i])
v[i]=v[i-c[j]]+1;
b[i]=j;
}
}
int s=0;
int p=k;
while (b[p]>0)
{
s+=c[b[p]];
p-=c[b[p]];
}
if(s==k)
cout<<v[k];
else cout<<"-1";
}
prolazi 12 primera
vreme nije problem