#
Positive Subset Sum

#======================================================================= # Author: Isai Damier # Title: Positive Subset Sum # Project: geekviewpoint # Package: algorithms # # Statement: # Given a sequence of n positive numbers totaling to T, check # whether there exists a subsequence totaling to x, where x is less # than or equal to T. # # Time-complexity: pseudo-polynomial: O(n*x) # Space-complexity: O(x) # # Dynamic Programming Strategy: # # Let's call the given Sequence S for convenience. Solving this # problem, there are two approaches we could take. On the one hand, # we could look through all the possible sub-sequences of S to see if # any of them sum up to x. This approach, however, would take an # exponential amount of work since there are 2^n possible # sub-sequences in S. On the other hand, we could list all the sums # between 0 and x and then try to find a sub-sequence for each one # of them until we find one for x. This second approach turns out to # be quite a lot faster: O(n*T). Here are the steps: # # 0] Create a boolean array called sum of size x+1: # As you might guess, when we are done filling the array, all the # sub-sums between 0 and x that can be calculated from S will be # set to true and those that cannot be reached will be set to false. # For example if S={2,4,7,9} then sum[5]=false while sum[13]=true # since 4+9=13. # # 1] Initialize sum{} to false: # Before any computation is performed, assume/pretend that each # sub-sum is unreachable. We know that's not true, but for now # let's be outrageous. # # 2] Set sum at index 0 to true: # This truth is self-evident. By taking no elements from S, we end # up with an empty sub-sequence. Therefore we can mark sum[0]=true, # since the sum of nothing is zero. # # 3] To fill the rest of the table, we are going to use the following # trick. Let S={2,4,7,9}. Then starting with 0, each time we find # a positive sum, we will add an element from S to that sum to get # a greater sum. For example, since sum[0]=true and 2 is in S, then # sum[0+2] must also be true. Therefore, we set sum[0+2]=sum[2]=true. # Then from sum[2]=true and element 4, we can say # sum[2+4]=sum[6]=true, and so on. # # Step 3 is known as the relaxation step. First we started with an # absurd assumption that no sub-sequence of S can sum up to any # number. Then as we find evidence to the contrary, we relax our # assumption. # # Alternative implementation: # This alternative is easier to read, but it does not halt for small x. # In the actual code, each for-loop checks for "not sum[x]" since that's # really all we care about and should stop once we find it. Also # this time complexity is O(n*T) and space complexity is O(T) # # sub_sum = [False] * ( x + 1 ) # sum[0] = True # for a in A: # for i in range(sum(A), a-1,-1): # T = sum(A) # if not sum[i] and sum[i - a]: # sum[i] = True #======================================================================= def positiveSubsetSum( A, x ): # preliminary if x < 0 or x > sum( A ): # T = sum(A) return False # algorithm sub_sum = [False] * ( x + 1 ) sub_sum[0] = True p = 0 while not sub_sum[x] and p < len( A ): a = A[p] q = x while not sub_sum[x] and q >= a: if not sub_sum[q] and sub_sum[q - a]: sub_sum[q] = True q -= 1 p += 1 return sub_sum[x]

import unittest from dynamic_programming import PositiveSubsequenceSum as algorithm class Test( unittest.TestCase ): def testPositiveSubsetSum( self ): S = [3, 5, 6] xTrue = [0, 3, 5, 6, 8, 9, 11, 14] for x in xTrue: self.assertTrue( algorithm.positiveSubsetSum( S, x ) ) xFalse = [1, 2, 4, 7, 10, 12, 13] for x in xFalse: self.assertFalse( algorithm.positiveSubsetSum( S, x ) )