#
The Partition Problem

/********************************************************************* * Author: Isai Damier * Title: Subset Sum: Divide Candies Evenly * 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 [make hyperlink]" problem is that here, instead of solving for a given weight * x, we are ask 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 array 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 check, until we * find sum[x]==true. * **********************************************************************/ package algorithm.programming.dynamic; public class CandyToKids { public int[] subsetSumDivideByTwo(int[] S) { //preliminary int T = 0; for (int a : S) { T += a; } int x = T / 2 + 1; boolean weight[] = new boolean[x + 1]; weight[0] = true; for (int a : S) { for (int i = x; i >= a; i--) { if (!weight[i] && weight[i - a]) { weight[i] = true; } } } for (int i = x; i >= 0; i--) { if (weight[i]) { return new int[]{i, T - i}; } } return null;//unreachable but needed for java. } }

package algorithm.programming.dynamic; import org.junit.Test; import static org.junit.Assert.*; public class CandyToKidsTest { /** * Test of subsetSumDivideByTwo method, of class CandyToKids. */ @Test public void testSubsetSumDivideByTwo() { System.out.println("subsetSumDivideByTwo"); CandyToKids instance = new CandyToKids(); int[] S = {3, 5, 7, 8, 11, 13, 17, 21, 34}; int[] expResult = {60, 59}; int[] result = instance.subsetSumDivideByTwo(S); assertArrayEquals(expResult, result); S = new int[]{3, 5, 7, 8, 13, 17, 21, 34}; expResult = new int[]{55, 53}; result = instance.subsetSumDivideByTwo(S); assertArrayEquals(expResult, result); S = new int[]{11, 29, 37, 45, 59, 67, 89, 97, 37}; expResult = new int[]{234, 237}; result = instance.subsetSumDivideByTwo(S); assertArrayEquals(expResult, result); } }