Pagini recente » Borderou de evaluare (job #2253798) | Cod sursa (job #1357883)
#include <fstream>
#include <cstdio>
#define DMAX 5010
#define NMAX 10010
using namespace std;
FILE*fin=fopen("rucsac.in", "r");
ofstream fout("rucsac.out");
int gmax, n;
int g[DMAX], p[DMAX];
int pmax[2][NMAX];
void citire();
void pd();
int main()
{
citire();
pd();
return 0;
}
void citire()
{
int i;
fscanf(fin, "%d%d", &n, &gmax);
for(i=1;i<=n;i++)
{
fscanf(fin, "%d%d", &g[i], &p[i]);
}
}
void pd()
{
int i, gt;
for(gt=1; gt <= gmax; gt++)
if(g[1] <= gt)
pmax[1][gt] = p[1];
for(i=2; i<=n; i++)
for(gt=1; gt<=gmax; gt++)
{
pmax[i%2][gt] = pmax[(i-1)%2][gt];
if(g[i] <= gt && pmax[(i-1)%2][gt-g[i]]+p[i] > pmax[i%2][gt])
pmax[i%2][gt] = pmax[(i-1)%2][gt-g[i]]+p[i];
}
fout<<pmax[n%2][gmax]<<'\n';
}