1

Реализую алгоритм решения задачи о рюкзаке с мемоизацией.

#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);
}

2 ответа 2

2
  1. В книге же написано массив v должен быть глобальным, то есть создаваться один раз и передаваться как параметр.
  2. Векторы вы передаете по указателю, а не по ссылке.
  3. Если вас смущает количество параметров засуньте их в структуру и передавайте указатель на нее, ну или сделайте их глобальными.
  4. Вот это никогда не закончится:

    for(int k = 0; i < j; k++){
       if(i == 0 || k == 0)
          v[i][k] = 0;
       else
          v[i][k] = -1;
    }
    

Мой вам совет сначала добейтесь чтобы код работал правильно, а затем его улучшайте, думайте про количество параметров и прочее. Как говорил великий Дейкстра, - "Преждевременная оптимизация - враг любого проекта".

И еще не большой совет: не стоит называть переменные одинаковыми именами, такой код очень трудно понимать.

3
  • Пытаюсь исправить программу. В конце ОП-поста добавил новый код и буду дальше его улучшать. Хорошо ли я начал проектировать класс?
    – typemoon
    6 дек 2015 в 17:19
  • @typemoon Должен работать
    – Cerbo
    7 дек 2015 в 9:10
  • Не работает. Падает. ideone.com/KmRwtc
    – typemoon
    7 дек 2015 в 15:00
0

Если у вас много параметров, разделите их на постоянную и переменную часть.

Заведите класс, постоянную часть (weights, values и мемоизацию, кажется) положите в класс, рекурсивную функцию превратите в приватный метод, и передавайте только i, j.

3
  • Не совсем понял, что это будет за класс. Почему метод приватный? Как он будет работать? Как создается класс, что передается в конструктор кроме i и j?
    – typemoon
    6 дек 2015 в 16:40
  • Добавил еще один скрин наверх. Там написано, что массив v инициализируется начальными значениями, и в этом процессе участвуют переменные i и j. А как это реализовать, если эти переменные каждый раз передаются в функцию при рекурсивном вызове? Как-то напутано в книге. Непонятно, как все это реализуется на языках типа C++.
    – typemoon
    6 дек 2015 в 16:48
  • Вот такая программа крашится. ideone.com/KmRwtc
    – typemoon
    6 дек 2015 в 18:10

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.