Cod sursa(job #2090157)
Utilizator | Data | 17 decembrie 2017 17:36:23 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 5010
#define MAXG 10010
int N, G, Pmax;
int W[MAXN], P[MAXN];
int D[MAXG],ans=-1;
int main()
{
freopen("rucsac.in", "r",stdin);
freopen("rucsac.out","w",stdout);
scanf("%d%d", &N, &G);
for(int i = 1; i <= N; ++i)
scanf("%d%d", &W[i], &P[i]);
for(int i = 1 ;i <= N ; ++i)
for(int cw = G ; cw >= W[i] ; --cw)
{
D[cw]=max(D[cw],D[cw-W[i]]+P[i]);
ans=max(ans,D[cw]);
}
printf("%d",ans);
return 0;
}