Cod sursa(job #1131194)
Utilizator | Mircea Popovici mircea98ro | Data | 28 februarie 2014 18:23:22 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define N 10001
int profit[N];
bool verif();
int n,G,w[N],p[N],i,g,maxx;
int main()
{
fin>>n>>G;
for (i=1;i<=n;i++)
fin>>w[i]>>p[i];
for (i=1;i<=n;i++)
{
for (g=G-w[i];g>=0;g--)
if (profit[w[i]+g]<profit[g]+p[i])
profit[w[i]+g]=profit[g]+p[i], maxx=(profit[w[i]+g]>maxx?profit[w[i]+g]:maxx);
}
fout<<maxx<<'\n';
fout.close();
return 0;
}