Реализация псевдополиномиального DP Subset Sum

Question

Я пытался реализовать алгоритм, предложенный на странице Википедии, для алгоритма псевдополиномиального времени для суммы подмножеств , где мы стремимся определить, существует ли непустое подмножество {x_1, ..., x_N}который суммирует до нуля. Таким образом, мы устанавливаем диапазон от суммы отрицательных чисел (A) до суммы положительных чисел (B) и создаем матрицу для хранения значений Q (i, s) для 1 ≤ i ≤ N и A ≤ s≤ B. Затем для его заполнения мы должны сначала установить Q (1, s): = (x_1 == s), а для рекурсивного случая установить Q (i, s): = Q (i - 1, s) или (xi == s) или Q (i - 1, s - xi), для A ≤ s ≤ B.

Вот мой снимок, где inp содержит входной набор. Я отслеживаю «реальный» индекс s в переменной arrindex, потому что s может быть некоторым отрицательным числом, и я не могу индексировать векторы с отрицательным значением.

vector<vector<bool>> result (inp.size(), vector<bool>(abs(B-A)+1)); // initialize results matrix
for(int s = A,arrindex=0; s <= B; s++,arrindex++){
    if(s == inp[0])
        result[0][arrindex] = true;
for(int i = 1; i < inp.size(); i++){
    for(int s = A,arrindex=0; s <= B; s++,arrindex++){
        // CHECK: Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi),  for A ≤ s ≤ B
        if(s == inp[i] || result[i-1][arrindex] || result[i-1][abs((s - inp[i])-A)])
            result[i][arrindex] = true;
    }
}

Моя попытка дает ответ, ноэто часто кажется неправильным. В качестве простого примера, если мой ввод {-2, 1}, ответ должен быть нет, но полученная мной матрица

1 0 0 0
1 1 0 1

Что, я думаю, будет означать «да», верно? Итак, мой вопрос, я реализовал это неправильно? Или я неправильно интерпретирую?

Answer 1

Я думаю, что термин result[i - 1][abs((s - inp[i]) - A)] не является правильным. Это должно быть:

A <= s - inp[i] && s - inp[i] <= B && result[i - 1][s - inp[i] - A]

Вы можете избежать вложенных vector s, используя простую лямбда-функцию для имитации матрицы:

const auto n_rows = inp.size();
const auto n_cols = static_cast<std::size_t>(B - A + 1);
auto q = [qm = std::vector<bool>(n_rows * n_cols), n_rows, A]
         (auto i, auto j) mutable
         { return qm[i + (j - A) * n_rows]; };

for (auto j = A; j <= B; ++j)
    q(0, j) = (inp[0] == j);

for (std::size_t i = 1; i < n_rows; ++i)
    for (auto j = A; j <= B; ++j)
        q(i, j) = (inp[i] == j || q(i - 1, j) || 
                  (A <= j - inp[i] && j - inp[i] <= B && q(i - 1, j - inp[i])));

const bool has_zero_subset = q(n_rows - 1, 0);