Cod sursa(job #2376878)
Utilizator | Tudose Sanziana TudoseSanziana | Data | 8 martie 2019 18:21:34 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int N_MAX = 5e3, G_MAX = 5e4;
int n, g;
int gr, pr;
int ans;
int dp[G_MAX + 2];
int main() {
in >> n >> g;
for(int i = 1; i <= g; i++)
dp[i] = -1;
for(int i = 1; i <= n; i++) {
in >> gr >> pr;
for(int j = g; j >= 0; j--)
if(dp[j] != -1 && j + gr <= g)
dp[j + gr] = max(dp[j + gr], dp[j] + pr);
}
for(int i = 1; i <= g; i++)
ans = max(ans, dp[i]);
out << ans << '\n';
return 0;
}