Cod sursa(job #771051)
Utilizator | Tutuianu George geobarosanu1 | Data | 24 iulie 2012 17:27:39 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <stdio.h>
int max(int a, int b){
if (a>b)
return a;
return b;
}
int dp[10000][5001];
int main(){
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
int N, G;
scanf("%d %d", &N, &G);
int w[5001], p[5001];
for (int i=1; i<=N; ++i)
scanf("%d %d", &w[i], &p[i]);
for (int i=1; i<=N; ++i){
for (int j=0; j<=G; ++j){
if (w[i] <= j)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
}
}
printf("%d", dp[N][G]);
return 0;
}