0

I was learning subset sum problem ,and i'd like to ask some question here

(1) Subset Sum algorithm

I read the C code in this link just now,and I wonder that why author can define?

S[i,0]=true ,S[0,j]=false

S[i,0] means the subset[1,...i] that sums to 0,why can it assign to true.?And how can I modify this algorithm if want to print the content of subset? Because it seemed forbidden to chat with author privately,I have to post it .

(2)if there are negative numbers in array,I have tried to test that it is not fit.How can I define the initial value for S[i,0] and S[0,j]?

Could anyone help me to clarify?

Thanks in advance!

Community
  • 1
  • 1
liumilan
  • 365
  • 1
  • 4
  • 13

1 Answers1

1

There is a problem with the base clause suggested, since with it, you could also take s[n,0] as an initial value.

A better stop clause to the recursive formula of subset-sum is s[i,xi] = true. The idea is simple, the set {x1,x2,...,xi} contains a subset that sums to xi - it is the subset {xi}. The recursion will later on take care of the rest, and if there is a subset summing to 0, it will find it.

According to this approach, the base clause is:

s[i,xi] = true (for each i)
s[0,j] = false (for each j)

And the recursive formula is:

s[i,j] = s[i-1,j] OR s[i-1,j-xi]

To get which elements are actually in the subset, you will need to follow the matrix you built with your dynamic programming. "follow" the choices done by the matrix, and stick to a path that yields true until you find a "stop clause" (s == xi)

It can be described recursively with:

getSubset(i,s):
   if s[i-1,s]: //there is a solution without choosing xi
       return getSubset(i-1, s)
   if (xi == s): //true base clause
        l <- new list
        l.append(xi)
        return l
   if s[i -1, s-xi]: //there is a solution when choosing xi
        l <- getSubset(i-1,s-xi)
        l.append(xi)
        return l

It resembles a lot (make sure you understand why): How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • can it cost much more space if want to define s[i,xi]=true?because the value of xi may be very large.And the sum may be not so large,smaller. – liumilan Jan 04 '13 at 16:13
  • @liumilan: No, it won't cost more space. At some point you will have to calculate s[i,xi] in both approaches - and thus this value must be stored anyway. Note that you raise an important issue with this solution - it is *pseudo-polynomial*, i.e. the time (and space) it consumes depends linearly on the numbers in the subsets - which are exponential in the number of bits needed to represent them. – amit Jan 04 '13 at 16:15