#
The Partition Problem

#======================================================================= # Author: Isai Damier # Title: Two Way Partition # Project: geekviewpoint # Package: algorithms # # Statement: # Given n bags of candies, divide the candies between two kids # as evenly as possible without splitting individual bags. The candies # are valued by weight, in ounce (oz). # # Time Complexity: O(n*w) # where w is the total weight of all the candies together. # # Dynamic Programming Strategy: # # The difference between this problem and the "Positive Subsequence # Sum" problem is that here, instead of solving for a given weight # x, we are asked to come up with x given the constraint that x must # be as close to T/2 as possible. # # So let's do this. Instead of wasting too much time thinking about x, # let x = T/2 so that we can proceed as we did for the "Positive # Subsequence Sum" problem. Then after we are done filling sum[] # completely, we will walk the list backward until we find a positive # weight. For our illustration, we will use sequence S=[2,4,7,9]. # 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 # because 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 array, we are going to use the following # trick. 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. # # 4] Recall that we decided to let x=T/2. In an ideal world, we will # split the candies and the kids will get exactly the same amount. # But since that's not likely to happen in real life, here is a # sensible strategy. After we finish filling the sum[] array, starting # at x=T/2 we will check to see if sum[x] equals true. If it is, we # are done. If not, we decrease x by one and keep checking, until we # find sum[x]==true. #======================================================================= def subsetSumDivideByTwo( S ): # preliminary T = 0 for a in S: T += a x = T / 2 + 1 weight = [False] * ( x + 1 ) weight[0] = True for a in S: for i in range( x, a - 1, -1 ): if not weight[i] and weight[i - a]: weight[i] = True for i in range( x, -1, -1 ): if weight[i]: return [i, T - i]

import unittest from dynamic_programming import TwoPartitionProblem as two_partition class Test( unittest.TestCase ): def testSubsetSumDivideByTwo( self ): S = [3, 5, 7, 8, 11, 13, 17, 21, 34] expResult = [60, 59] result = two_partition.subsetSumDivideByTwo( S ) self.assertEquals( expResult, result ) S = [3, 5, 7, 8, 13, 17, 21, 34] expResult = [55, 53] result = two_partition.subsetSumDivideByTwo( S ) self.assertEquals( expResult, result ) S = [11, 29, 37, 45, 59, 67, 89, 97, 37] expResult = [234, 237] result = two_partition.subsetSumDivideByTwo( S ) self.assertEquals( expResult, result )