algorithm - pisinger对subsetsum算法的修改

Question

我正在查看 pisinger 的算法，详见此处

Fast solution to Subset sum algorithm by Pisinger

在维基百科上http://en.wikipedia.org/wiki/Subset_sum_problem

For the case that each xi is positive and bounded by a fixed constant C, Pisinger found a linear time algorithm having time complexity O(NC).[3] (Note that this is for the version of the problem where the target sum is not necessarily zero, otherwise the problem would be trivial.)

他的方法似乎有两个限制。第一个特别指出任何输入中的所有值都必须是 <= C .

在我看来，仅凭该约束，这不是可以解决原始子集和问题(没有限制)的算法。

但是假设C=1000000例如。然后在我们甚至在输入列表上运行算法之前。我们不能只将每个元素除以某个数字 d (也将目标总和除以 d)这样输入列表中的每个数字都是 <= C . 当算法返回某个子集时 s , 我们只是将 s 中的每个元素相乘通过 d .我们将拥有真正的子集。

有了这个观察，感觉我们需要那个 C 似乎不值得一提。约束。或者至少说输入可以更改 W.L.O.G(不失一般性)。所以无论输入如何，我们仍然可以解决同样的问题。换句话说，这种限制并没有使问题变得更难。所以实际上他的算法唯一的限制是它只能处理数字 >=0 .

我说得对吗？

谢谢

Answer 1

adrian.budau 说的是正确的。

在多项式解中， 在你说的除法之后，数组的每个值都应该保持为整数。 否则 DP 解决方案不再有效，因为项目值用作 DP 数组中的索引。

以下是我对子集和问题 (C=ELEMENT_MAX_VALUE) 的多项式 (DP) 解决方案

bool subsetsum_dp(VI& v, int sum)
{
    const int MAX_ELEMENT = 100;
    const int MAX_ELEMENT_VALUE = 1000;
    static int dp[MAX_ELEMENT+1][MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, -1, sizeof(dp));

    int n = S(v);
    dp[0][0] = 1, dp[0][v[0]] = 1;//include, excluse the value
    FOR(i, 1, n)
    {
        REP(j, MAX_ELEMENT*MAX_ELEMENT_VALUE + 1)
        {
            if (dp[i-1][j] != -1) dp[i][j] = 1, dp[i][j + v[i]] = 1;//include, excluse the value
        }
    } 
    if (dp[n-1][sum] == 1) return true;
    return false;
}