Cod sursa(job #2485609)
Utilizator | Dogaru Roxana dogaru_roxana | Data | 1 noiembrie 2019 20:01:47 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.7 kb |
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int gr[5010], val[5010], n, gmax, i, j, a[5010][10010];
int main()
{
fin>>n>>gmax;
for (i=1; i<=n; i++)
fin>>gr[i]>>val[i];
for (i=1; i<=n; i++)
{
for (j=0; j<=gmax; j++)
{
if (gr[i]>j)
a[i][j]=a[i-1][j];
else
{
if (a[i-1][j-gr[i]]+val[i]>a[i-1][j])
a[i][j]=a[i-1][j-gr[i]]+val[i];
else
a[i][j]=a[i-1][j];
}
}
}
fout<<a[n][gmax];
fin.close();
fout.close();
return 0;
}