实现伪多项式 DP 子集和

Question

我尝试实施维基百科页面上针对 pseudo-polynomial time algorithm for subset sum 提出的算法，我们旨在确定是否存在 {x_1, ..., x_N 的非空子集} 总和为零。所以我们设置一个从负数之和 (A) 到正数之和 (B) 的范围，并创建一个矩阵来保存值 Q(i, s) for 1 ≤ i ≤ N and A ≤ s ≤ B。然后为了填充它，我们应该首先设置 Q(1, s) := (x_1 == s)，对于递归情况，我们设置 Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi), 对于 A ≤ s ≤ B.

这是我的镜头，其中 inp 包含输入集。我在变量 arrindex 中跟踪 s 的 "real" 索引，因为 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}，答案应该是no，但是我得到的矩阵是

1 0 0 0
1 1 0 1

我认为这会指示 "yes"，对吗？所以我的问题是，我是否错误地实施了这个？还是我理解有误？

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]

您可以使用简单的 lambda 函数模拟矩阵来避免嵌套 vector：

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

实现伪多项式 DP 子集和

Implementing Pseudopolynomial DP Subset Sum

c++

algorithm

dynamic-programming

subset-sum