Modification to subsetsum algorithm by pisinger

Question

I was looking at the algorithm by pisinger as detailed here

Fast solution to Subset sum algorithm by Pisinger

and on wikipedia 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.)

It seems that, with his approach, there are two constraints. The first one in particular says that all values in any input, must be <= C.

It sounds to me that, with just that constraint alone, this is not an algorithm that can solve the original subset sum problem (with no restrictions).

But suppose C=1000000 for example. Then before we even run the algorithm on the input list. Can't we just divide every element by some number d (and also divide the target sum by d too) such that every number in the input list will be <= C. When the algorithm returns some subset s, we just multiply every element in s by d. And we will have our true subset.

With that observation, it feels like it not worth mentioning that we need that C constraint. Or at least say that the input can be changed W.L.O.G (without loss of generality). So we can still solve the same problem no matter the input. That constraint is not making the problem any harder in other words. So really his algorithms only constraint is that it can only handle numbers >=0.

Am I right?

Thanks

In the beginning of the wikipedia article it says: "The problem is this: given a set (or multiset) of integers". If you divide the numbers by a constant "d" they might not remain integers. — adrian.budau, Jun 29 '14 at 06:43
I don't know the algorithm, but from what you wrote I guess it makes use of the fact that there are only finitely many possibilities for each element. This number of possibilities would not change if you divide by some constant. — Henry, Jun 29 '14 at 06:45

score 0 · Answer 1 · answered Dec 06 '14 at 19:09

What adrian.budau said is correct.

In Polynomial solution, every value of array should remain as integer after the division you said. otherwise DP solution does not work anymore, because item values are used as index in DP array.

Following is my Polynomial(DP) solution for subsetsum problem(C=ELEMENT_MAX_VALUE)

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

Modification to subsetsum algorithm by pisinger

1 Answers1