Cod sursa(job #2376871)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 8 martie 2019 18:17:23
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 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] = dp[j] + pr;
    }

    for(int i = 1; i <= g; i++)
        ans = max(ans, dp[i]);

    out << ans << '\n';

    return 0;
}