Cod sursa(job #1818522)
Utilizator | Stan Flavius Stefan stan_flavius | Data | 29 noiembrie 2016 13:30:35 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 35 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,c[5001][5001];
struct obiect
{ int c,g;};
obiect a[5001];
void citire()
{ int i;
fin>>n>>G;
for(i=1; i<=n; ++i)
fin>>a[i].g>>a[i].c;
}
void dinamica()
{ int i,j;
for(i=1; i<=n; ++i)
for(j=1; j<=G; ++j)
if(a[i].g>j) c[i][j]=c[i-1][j];
else c[i][j]=max(c[i-1][j],a[i].c+c[i-1][j-a[i].g]);
fout<<c[n][G];
}
int main()
{ citire();
dinamica();
return 0;
}