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


class Knapsack{
private:
	vector<int> weights;
	vector<int> values;
	int n, w;
	//int **v;
	vector< vector<int> > v;
public:
	Knapsack(vector<int> wt, vector<int> val, int n, int cap){
		// Сохранение переданных векторов, числа элементов и вместимости ранца
		weights.assign(wt.begin(), wt.end());
		values.assign(val.begin(), val.end());
		this->n = n;
		this->w = cap;
		// Создание таблицы мемоизации и заполнение начальными значениями
		/*v = new int * [n];
		for(int i = 0; i < n; i++)
			v[i] = new int [w];*/
		v = vector<n, vector<int>(w));
		// Инициализирование таблицы
		for(int i = 0; i < n; i++)
			for(int j = 0; j < w; j++)
				v[i][j] = -1;
		// Инициализирование нулями первой строки и первого столбца
		for(int i = 0; i < w; i++)
			v[0][i] = 0;
		for(int i = 0; i < n; i++)
			v[i][0] = 0;
	}
	~Knapsack(){
		//for(int i = 0; i < n; i++)
		//	delete[] v[i];
		//delete[] v;
	}

	int knapsack_solver(int i, int j);
	int solve();
};

int Knapsack::knapsack_solver(int i, int j){
	int value;
	if(v[i][j] < 0){
		if(j < weights[i])
			value = knapsack_solver(i - 1, j);
		else
			value = max(knapsack_solver(i - 1, j),
						values[i] + knapsack_solver(i - 1, j - weights[i]));
		v[i][j] = value;
	}
	return v[i][j];
}

int Knapsack::solve(){
	return knapsack_solver(n, w);
}

int main(){
	int n = 4, cap = 5;
	int w[4] = {2, 1, 3, 2};
	int v[4] = {12, 10, 20, 15};
	vector<int> wt(w, w + 4);
	vector<int> val(v, v + 4);

	Knapsack knap(wt, val, n, cap);
	cout << knap.solve() << endl;

	int pause;
	cin >> pause;

	return 0;
}