zaino.cpp

#include <iostream>
#include <fstream>
using namespace std;

const int DIM = 100000;
const int INF = 100000;

int V[DIM], P[DIM];
long long int ** DP;

long long int zaino(int n, int C);
long long int zainoRec(int i, int C);

int main(){
    ifstream in("input.txt");
    ofstream out("output.txt");

    int c, n;

    in >> c >> n;

    for(int i = 0; i < n; i++){
        in >> P[i] >> V[i];
        cout << P[i] << " " << V[i] << endl;
    }

    long long int res = zaino(n, c);

    cout << res << endl;
    out << res;

    return 0;
}

long long int max(long long int a, long long int b){
    return (a > b) ? a : b;
}

long long int zaino(int n, int C){
    DP = new long long int *[n];
    for(int i = 0; i < n; i++)
        DP[i] = new long long int [C];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < C; j++)
            DP[i][j] = -1;
    }
    return zainoRec(n, C);
}

long long int zainoRec(int i, int C){
    if(C == 0 || i == 0){
        return 0;
    } else if (C < 0) {
        return -INF;
    }

    if(DP[i][C] < 0){
        int notTaken = zainoRec(i-1, C);
        int taken = V[i] + zainoRec(i-1, C-P[i]);
        DP[i][C] = max(notTaken, taken);
    }
    cout << "i= " << i << ", C= " << C << " --> " << DP[i][C] << endl;
    return DP[i][C];
}