Pagini recente » Cod sursa (job #2178951) | Cod sursa (job #795628) | Cod sursa (job #715028)
Cod sursa(job #715028)
#include <fstream>
using namespace std;
ifstream f ("energii.in");
ofstream g ("energii.out");
int n,i,j,k,W,e[1003],c[1003],sol[10000000];
char p[10000][1002];
void citire()
{
f>>n>>W;
for(i=0;i<n;i++) f>>e[i]>>c[i];
f.close();
}
int main()
{
bool gasit=0;
citire();
for(i=1;i<=10000;i++) sol[i]=-1;
for(i=0;!gasit && i<10000;i++)
{
for(j=0;j<n && !gasit;j++)
{
if(c[j]<=i && sol[i-c[j]]!=-1 && !p[i-c[j]][j])
{
if(sol[i-c[j]]+e[j]>sol[i])
{
sol[i]=sol[i-c[j]]+e[j];
for(k=0;k<n;k++) p[i][k]=p[i-c[j]][k];
p[i][j]=1;
if(sol[i]>=W) gasit=1;
}
}
}
}
if(!gasit) g<<"-1"<<"\n";
else g<<i-1;
f.close();
g.close();
return 0;
}