Cod sursa(job #1979713)
Utilizator | Taut Radu Alexandru Sunt_3l3v | Data | 11 mai 2017 10:26:50 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int d[10005];
int main()
{
int GMAX,i,g,p,j,last,n,maxv=0;
in>>n>>GMAX;
for(i=1;i<=GMAX;i++)
d[i]=-1;
d[0]=0;
last=0;
for(i=1;i<=n;i++)
{
in>>g>>p;
for(j=last;j>=0;j--)
if(d[j]!=-1 && j+g <= GMAX)
if(d[j+g]<d[j]+p)
{
d[j+g]=d[j]+p;
if(j+g>last)
last=j+g;
}
}///for i
for(i=1;i<=GMAX;i++)
{
if(maxv<d[i])
maxv=d[i];
}
out<<maxv;
return 0;
}