#
Subset Sum with Endless Supplies

/********************************************************************* * Author: Isai Damier * Title: Subset Sum with Endless Supplies * Project: geekviewpoint * Package: algorithms * * Statement: * Given a sequence S, with n positive numbers totaling to T, check * whether there exists a subsequence totaling to x, where x is less * than or equal to T. You may use any of the elements in S more than * once. * * Time-complexity: pseudo-polynomial: O(n*x) * Space-complexity: O(x) * * Dynamic Programming Strategy: * * We are not going to say too much here since this is essentially the * "Positive Subset Sum" problem. So we will wait right here as you * go read the "Positive Subset Sum" implementation. * * Okay. So there is one distinction between the two problems: here you * may use each elements as many times as you need. So given the sequence * S={2,8,24}, we can reach 6 as 2+2+2 or 20 as 8+8+2+2. * * To achieve this multiplicity, all we have to change is the direction * of the nested for-loop so that we end up with: * * for(int e : S) * for(int i=0; i<=x; i++) * if(sum[i]) * sum[i+e]=true; * * The reason it's that simple is because the line "if(sum[i])" is * most of the time looking at multiples. For instance, during the first * pass of the outer for-loop (i.e. e=2), the second for-loop sets all * multiples of 2 to true. Manually run the example where S={2,8,24} * and x=18 if you still don't see it. **********************************************************************/ package algorithm.programming.dynamic; public class SubsetSumWithMultipleSupplies { public boolean subsetSumEndlessReuse(int[] S, int x) { //preliminary int T = 0; for (int e : S) { T += e; } if (x < 0 || x > T) { return false; } //algorithm boolean sum[] = new boolean[x + 1]; sum[0] = true; for (int p = 0; !sum[x] && p < S.length; p++) { int e = S[p]; for (int q = 0; !sum[x] && q <= x; q++) { if (q + e <= x && sum[q]) { sum[q + e] = true; } } } return sum[x]; } }

package algorithm.programming.dynamic; import org.junit.Test; import static org.junit.Assert.*; public class SubsetSumWithMultipleSuppliesTest { /** * Test of subsetSumEndlessReuse method, * of class SubsetSumWithMultipleSupplies. */ @Test public void testPositiveSubsetSum() { System.out.println("subsetSumEndlessReuse"); int[] S = {2, 8, 24}; SubsetSumWithMultipleSupplies instance = new SubsetSumWithMultipleSupplies(); for (int x = 24 + 8 + 2; x >= 0; x = -2) { assertTrue(instance.subsetSumEndlessReuse(S, x)); } for (int x = 24 + 8 + 2 - 1; x >= 1; x = -2) { assertFalse(instance.subsetSumEndlessReuse(S, x)); } } }