Cod sursa(job #1542060)
Utilizator | Alex Dima AlexDima | Data | 4 decembrie 2015 22:27:11 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <fstream>
using namespace std;
const int MAX=5e3+14;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int vg[MAX];
int vp[MAX];
int rep[1e4+14];
int main()
{
int n,g,w,i,j=1,max=0;
fin>>n>>g;
for(int i=1;i<=n;i++)
{
fin>>vg[i]>>vp[i];
}
for(i=1;i<=n;i++)
for(j=g-vg[i];j>=0;--j)
if(rep[j+vg[i]]<rep[j]+vp[i])
{
rep[j+vg[i]]=rep[j]+vp[i];
if(max<rep[j+vg[i]])max=rep[j+vg[i]];
}
fout<<max;
return 0;
}