Cod sursa(job #788517)
Utilizator | Data | 15 septembrie 2012 11:10:53 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
#define MAXN 5005
#define MAXG 10005
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int mx,n,G,w[MAXN],p[MAXN],pd[MAXG];
int main()
{
int i,j;
f>>n>>G;
for(i=1;i<=n;i++)
f>>w[i]>>p[i];
for(i=1;i<=n;i++){
for(j=G;j>=w[i];j--)
if(pd[j-w[i]]+p[i]>pd[j])
pd[j]=pd[j-w[i]]+p[i];}
for(i=0;i<=MAXG;i++)
if(pd[i]>mx)
mx=pd[i];
g<<mx<<'\n';
f.close();
g.close();
return 0;
}