Nu aveti permisiuni pentru a descarca fisierul grader_test10.in
Cod sursa(job #822581)
Utilizator | ahmed.abdrabo ahmed.abdrabo | Data | 23 noiembrie 2012 19:40:26 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <iostream>
#include <fstream>
using namespace std;
int N, G, W[5000], P[5000];
int dp[2][10001];
int main() {
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
cin >> N >> G;
for (int i = 1; i <= N; i++) {
cin >> W[i] >> P[i];
}
for (int i = 1; i <= N; i++) {
for (int w = 0; w <= G; w++) {
dp[i & 1][w] = dp[(i - 1) & 1][w];
if (W[i] <= w) {
dp[i & 1][w] = max(dp[i & 1][w], P[i] + dp[(i - 1) & 1][w - W[i]]);
}
}
}
cout << dp[N & 1][G] << endl;
return 0;
}