Cod sursa(job #2007577)
Utilizator | Todoran Alexandru Raul alextodoran | Data | 3 august 2017 13:06:09 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 35 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <iostream>
#include <fstream>
#define DN 5002
using namespace std;
int n,G,i,j,mx,g[DN],v[DN],d[10002][DN];
int main()
{
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
fin>>n>>G;
for(i=1;i<=n;i++)
{
fin>>g[i]>>v[i];
}
for(i=0;i<=G;i++)
{
for(j=0;j<n;j++)
{
if(i+g[j+1]<=G)
d[i+g[j+1]][j+1]=max(d[i][j]+v[j+1],d[i+g[j+1]][j+1]);
d[i][j+1]=max(d[i][j+1],d[i][j]);
}
}
for(i=1;i<=G;i++)
{
if(d[i][n]>mx)mx=d[i][n];
}
fout<<mx<<"\n";
return 0;
}