Cod sursa(job #1569032)
Utilizator | Bumbu Alexandru Guzglete | Data | 14 ianuarie 2016 21:57:00 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int g[5010], p[5010], rez[10010];
int N,G;
int main()
{
int i,j;
fin>>N>>G;
for (i=1;i<=N;i++)
fin>>g[i]>>p[i];
for (i=1;i<=N;i++)
{
j=G;
while (j >= g[i])
{
if (p[i]+rez[j-g[i]] > rez[j])
rez[j] = p[i]+rez[j-g[i]];
j--;
}
}
int max=0;
for (i=1;i<=G;i++)
if (rez[i]>max)
max=rez[i];
fout<<max;
return 0;
}