#include <iostream>

int getRandomNumber(int min, int max);
int G(int k, int r, int*, int*);

int n = 9;

int main() {
    std::cout << "Hello, World!" << std::endl;
    //int n,
            int w;
    //n = getRandomNumber(0, 10);
    //n = 9;
    int s[n];
    int p[n];
    for (int i = 0; i < n; ++i) {
        //s[n] = getRandomNumber(0, 10);
        s[i] = i + 1;
        p[i] = i + 1;
        //p[n] = getRandomNumber(0, 10);
    }
    //w = getRandomNumber(0, 10);
    w = 6;
    std::cout << "n -> " << n << "\tw -> "<<w<<"\n";
    std::cout << "G(n,w) -> " << G(n, w, s, p);
    return 0;
}

int G(int k, int r, int *s, int *p){
    if(k==0||r==0)
        return 0;
    if(s[k]>r)
        return G(k-1, r, s, p);
    return std::max(G(k-1, r, s, p), p[k] + G(k-1, r - s[k], s, p));
}

int getRandomNumber(int min, int max) {
    static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
    return min + static_cast<int>((max - min + 1) * (rand() * fraction));
}