#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];*/
vector< vector<int> > tmp(n, vector<int>(w));
v.assign(tmp.begin(), tmp.end());
// Инициализирование таблицы
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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgS25hcHNhY2t7CnByaXZhdGU6Cgl2ZWN0b3I8aW50PiB3ZWlnaHRzOwoJdmVjdG9yPGludD4gdmFsdWVzOwoJaW50IG4sIHc7CgkvL2ludCAqKnY7Cgl2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gdjsKcHVibGljOgoJS25hcHNhY2sodmVjdG9yPGludD4gd3QsIHZlY3RvcjxpbnQ+IHZhbCwgaW50IG4sIGludCBjYXApewoJCS8vINCh0L7RhdGA0LDQvdC10L3QuNC1INC/0LXRgNC10LTQsNC90L3Ri9GFINCy0LXQutGC0L7RgNC+0LIsINGH0LjRgdC70LAg0Y3Qu9C10LzQtdC90YLQvtCyINC4INCy0LzQtdGB0YLQuNC80L7RgdGC0Lgg0YDQsNC90YbQsAoJCXdlaWdodHMuYXNzaWduKHd0LmJlZ2luKCksIHd0LmVuZCgpKTsKCQl2YWx1ZXMuYXNzaWduKHZhbC5iZWdpbigpLCB2YWwuZW5kKCkpOwoJCXRoaXMtPm4gPSBuOwoJCXRoaXMtPncgPSBjYXA7CgkJLy8g0KHQvtC30LTQsNC90LjQtSDRgtCw0LHQu9C40YbRiyDQvNC10LzQvtC40LfQsNGG0LjQuCDQuCDQt9Cw0L/QvtC70L3QtdC90LjQtSDQvdCw0YfQsNC70YzQvdGL0LzQuCDQt9C90LDRh9C10L3QuNGP0LzQuAoJCS8qdiA9IG5ldyBpbnQgKiBbbl07CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQkJdltpXSA9IG5ldyBpbnQgW3ddOyovCgkJdmVjdG9yPCB2ZWN0b3I8aW50PiA+IHRtcChuLCB2ZWN0b3I8aW50Pih3KSk7CgkJdi5hc3NpZ24odG1wLmJlZ2luKCksIHRtcC5lbmQoKSk7CgkJLy8g0JjQvdC40YbQuNCw0LvQuNC30LjRgNC+0LLQsNC90LjQtSDRgtCw0LHQu9C40YbRiwoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJCWZvcihpbnQgaiA9IDA7IGogPCB3OyBqKyspCgkJCQl2W2ldW2pdID0gLTE7CgkJLy8g0JjQvdC40YbQuNCw0LvQuNC30LjRgNC+0LLQsNC90LjQtSDQvdGD0LvRj9C80Lgg0L/QtdGA0LLQvtC5INGB0YLRgNC+0LrQuCDQuCDQv9C10YDQstC+0LPQviDRgdGC0L7Qu9Cx0YbQsAoJCWZvcihpbnQgaSA9IDA7IGkgPCB3OyBpKyspCgkJCXZbMF1baV0gPSAwOwoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJCXZbaV1bMF0gPSAwOwoJfQoJfktuYXBzYWNrKCl7CgkJLy9mb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJCS8vCWRlbGV0ZVtdIHZbaV07CgkJLy9kZWxldGVbXSB2OwoJfQoKCWludCBrbmFwc2Fja19zb2x2ZXIoaW50IGksIGludCBqKTsKCWludCBzb2x2ZSgpOwp9OwoKaW50IEtuYXBzYWNrOjprbmFwc2Fja19zb2x2ZXIoaW50IGksIGludCBqKXsKCWludCB2YWx1ZTsKCWlmKHZbaV1bal0gPCAwKXsKCQlpZihqIDwgd2VpZ2h0c1tpXSkKCQkJdmFsdWUgPSBrbmFwc2Fja19zb2x2ZXIoaSAtIDEsIGopOwoJCWVsc2UKCQkJdmFsdWUgPSBtYXgoa25hcHNhY2tfc29sdmVyKGkgLSAxLCBqKSwKCQkJCQkJdmFsdWVzW2ldICsga25hcHNhY2tfc29sdmVyKGkgLSAxLCBqIC0gd2VpZ2h0c1tpXSkpOwoJCXZbaV1bal0gPSB2YWx1ZTsKCX0KCXJldHVybiB2W2ldW2pdOwp9CgppbnQgS25hcHNhY2s6OnNvbHZlKCl7CglyZXR1cm4ga25hcHNhY2tfc29sdmVyKG4sIHcpOwp9CgppbnQgbWFpbigpewoJaW50IG4gPSA0LCBjYXAgPSA1OwoJaW50IHdbNF0gPSB7MiwgMSwgMywgMn07CglpbnQgdls0XSA9IHsxMiwgMTAsIDIwLCAxNX07Cgl2ZWN0b3I8aW50PiB3dCh3LCB3ICsgNCk7Cgl2ZWN0b3I8aW50PiB2YWwodiwgdiArIDQpOwoKCUtuYXBzYWNrIGtuYXAod3QsIHZhbCwgbiwgY2FwKTsKCWNvdXQgPDwga25hcC5zb2x2ZSgpIDw8IGVuZGw7CgoJaW50IHBhdXNlOwoJY2luID4+IHBhdXNlOwoKCXJldHVybiAwOwp9