Cod sursa(job #862185)
Utilizator | Alexandrescu Cristian bulbulica | Data | 22 ianuarie 2013 13:15:34 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include<fstream>
using namespace std;
#define Gmax 10000
#define Nmax 5000
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int A[Gmax],p,u,i,j,G[Nmax],P[Nmax],n,ga,sol;
int main()
{
f>>n>>ga;
for(i=1;i<=n;++i)
f>>G[i]>>P[i];
for(i=1;i<=n;++i)
for(j=ga;j>=0;--j)
if(j+G[i]<=ga && A[j+G[i]]<A[j]+P[i])
A[j+G[i]]=A[j]+P[i] ;
sol = 0 ;
for(i=1;i<=ga;++i)
if(A[i]>sol)
sol=A[i] ;
g<<sol;
}