Реализую алгоритм решения задачи о рюкзаке с мемоизацией.
#include <iostream>
#include <vector>
using namespace std;
int knapsack(const vector<int> *weights, const vector<int> *values, int n, int i, int j){
int value;
int **v = new int *[n];
for(int i = 0; i < j; i++)
v[i] = new int[n];
//Заполнение массива v начальынми значениями
for(int i = 0; i < n; i++)
for(int k = 0; i < j; k++){
if(i == 0 || k == 0)
v[i][k] = 0;
else
v[i][k] = -1;
}
if(v[i][j] < 0){
if(j < weights[i])
value = knapsack(weights, values, n, i - 1, j);
else
value = max(knapsack(weights, values, n, i - 1, j),
values[i] + knapsack(weights, values, n, i - 1, j - weights[i]);
v[i][j] = value;
}
return v[i][j];
}
int main(){
}
Мне здесь не нравится все. Слишком много аргументов функции: число имеющихся вещей n
и, может быть, было бы удобнее вместо двух векторов weights
и values
использовать один. Не нравится способ передачи этих векторов в функцию: чтобы стек не забивался, я передаю их по константной ссылке, но из-за этого внутри функции возникли ошибки. Таблица v
в каждом экземпляре функции при рекурсивном вызове создается заново и имеет разные размеры. Это плохо.
Как можно улучшить эту функцию?
Еще у меня непонимание вот в чем. Каким образом здесь используется мемоизация, если не видно, как возвращаются предвычисленные значения из таблицы? Мы сначала строим таблицу, а потом возвращаем нужное значение. Или условие if(v[i][j] < 0)
как раз и гарантирует нам, что нужное значение будет браться из предвычисленой таблицы, а не вычисляться каждый раз заново?
Привожу исходный псевдокод алгоритма:
class Knapsack{
private:
vector<int> weights;
vector<int> values;
int n, w;
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 < cap; i++)
v[i] = new 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 < w; 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);
}