SubsetSum (No Repetition) Problem - II (Coin change)

As introduced in one of the previous posts (subset sum problem introduction) subset sum problem can be solved in exponential by brute force method.  Below the problem will be solved using Dynamic programming to get to pseudo polynomial time complexity. Note that coin change algorithm is nothing but one of the variation of subset sum problem.

Variation 1

Checking whether there existing a subset or not, that sums up-to the given sum (target).

Solution

Say, f[ i, w] represents whether up-to elements have a subset that sums up-to "w" using first 'i' elements, then

                f[i, w] = False i <= 0

                              True if weights[i] == w

                              f[i-1, w] if weights[i] > w

                              f[i-1, w] || f[i-1, w-weights[i]]

 

And the above function has optimal substructure property and overlapped sub problems. So, it can be solved by using Dynamic Programming.

Variation 2

What are the total number of subsets that can sum up-to given sum (target)

Solution

Say, f[i, sum] represents the number of subsets that sums up-to given sum (target) using first 'i' elements, then

                    f[i, sum] = 0 if i <= 0

                                   0 if sum < 0

                                   1 if sum == 0

                                   f[i-1, sum] + f[i-1, sum - weights[i]]

 

And above method also has optimal substructure and overlapped sub problems.

Variation 3

Find the minimal elements that required to sums to given target.

Solution

Say, f[i, sum] finds the minimal number of elements that required using up-to 'i' elements that sums up-to "sum"

                   f[i, sum] = 0 if i <= 0

                                     0 if sum < 0

                                     1 if weights[i] == sum

                                     f[i-1, w] if weights[i] > sum, Or f[i-1, w-weights[i]] == 0
                                     f[i-1, w-weights[i]] + 1 if f[i-1, w] == 0

                                     min (f[i-1, w], f[i-1, w-weights[i]] + 1)
                                    

 

Below is the corresponding code and unit tests...

 

Code Snippet

14. public bool SubsetSum_NoRepetition_KnapsackSimplified_DP_Tabulated_Eager(int[] weights, int W)
15.         {
16.             this.Validate(weights, W);
17.             bool[][] DP_Memoization_Cache = new bool[weights.Length + 1][];
18.             for (int i = 0; i <= weights.Length; i++)
19.             {
20.                 DP_Memoization_Cache[i] = new bool[W + 1];
21.             }
22.             for (int i = 1; i <= weights.Length; i++)
23.             {
24.                 for (int w = 0; w <= W; w++)
25.                 {
26.                     /// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
27.                     /// f(i, w) = False if i <= 0
28.                     ///           OR True if weights[i-1] == w
29.                     ///           OR f(i-1, w) if weights[i-1] > w
30.                                ///OR f(i-1, w) || f(i-1, w-weights[i-1])
31.                     if (weights[i - 1] == w)
32.                     {
33.                         DP_Memoization_Cache[i][w] = true;
34.                     }
35.                     else
36.                     {
37.                         DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w];
38.                         if (!DP_Memoization_Cache[i][w])
39.                         {
40.                             if (w > weights[i - 1])
41.                             {
42.                                 DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w - weights[i - 1]];
43.                             }
44.                         }
45.                     }
46.                 }
47.             }
48.             return DP_Memoization_Cache[weights.Length][W];
49.         }
50.         public bool SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int W)
51.         {
52.             this.Validate(weights, W);
53.             //note 'row' index represents the number of weights been used
54.             //note 'colum' index represents the weight that can be achived using given
55.             //number of weights 'row'
56.             bool?[][] DP_Memoization_Cache = new bool?[weights.Length + 1][];
57.             for (int i = 0; i <= weights.Length; i++)
58.             {
59.                 DP_Memoization_Cache[i] = new bool?[W + 1];
60.                 for (int w = 0; w <= W; w++)
61.                 {
62.                     if (i != 0)
63.                     {
64.                         DP_Memoization_Cache[i][w] = null;
65.                     }
66.                     else
67.                     {
68.                         //can't get to weight 'w' using none of the given weights
69.                         DP_Memoization_Cache[0][w] = false;
70.                     }
71.                 }
72.                 DP_Memoization_Cache[i][0] = false;
73.             }
74.             bool f = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(
75.                 weights, w: W, i_rowIndexOfCache: weights.Length, DP_Memoization_Cache: DP_Memoization_Cache);
76.             Assert.IsTrue(f == DP_Memoization_Cache[weights.Length][W]);
77.             return f;
78.         }
79.         /// <summary>
80.         /// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
81.         /// f(i, w) = False if i < 0
82.         ///           OR True if weights[i] == w
83.         ///           OR f(i-1, w) if weights[i] > w
84.                    ///OR f(i-1, w) || f(i-1, w-weights[i])
85.         /// </summary>
86.         /// <param name="rowIndexOfCache">
87.         /// Note, its index of row in the cache
88.         /// index of given weifhts is indexOfCahce -1 (as it starts from 0)
89.         /// </param>
90.         bool SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int w, int i_rowIndexOfCache, bool?[][] DP_Memoization_Cache)
91.         {
92.             if (i_rowIndexOfCache < 0)
93.             {
94.                 return false;
95.             }
96.             if (DP_Memoization_Cache[i_rowIndexOfCache][w].HasValue)
97.             {
98.                 return DP_Memoization_Cache[i_rowIndexOfCache][w].Value;
99.             }
100.             int i_weights_index = i_rowIndexOfCache - 1;
101.             if (weights[i_weights_index] == w)
102.             {
103.                 //we can just use current weight, so no need to call other recursive methods
104.                 //just return true
105.                 DP_Memoization_Cache[i_rowIndexOfCache][w] = true;
106.                 return true;
107.             }
108.             //see if W, can be achieved without using weights[i]
109.             bool flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
110.                 w, i_rowIndexOfCache - 1);
111.             DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
112.             if (flag)
113.             {
114.                 return true;
115.             }
116.             if (w > weights[i_weights_index])
117.             {
118.                 //see if W-weight[i] can be achieved with rest of the weights
119.                 flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
120.                     w - weights[i_weights_index], i_rowIndexOfCache - 1);
121.                 DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
122.             }
123.             return flag;
124.         }
125.         public bool SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W)
126.         {
127.             this.Validate(weights, W);
128.             bool f = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W,
129.                 i: weights.Length - 1);
130.             return f;
131.         }
132.         /// <summary>
133.         /// f(i, w) = False if i < 0
134.         ///           OR True if weights[i] == w
135.         ///           OR f(i-1, w) if weights[i] > w
136.                    ///OR f(i-1, w) || f(i-1, w-weights[i])
137.         /// </summary>
138.         public bool SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W, int i)
139.         {
140.             if (i < 0)
141.             {
142.                 //no more weights to traverse
143.                 return false;
144.             }
145.             if (weights[i] == W)
146.             {
147.                 //we can just use current weight, so no need to call other recursive methods
148.                 //just return true
149.                 return true;
150.             }
151.             //see if W, can be achieved without using weights[i]
152.             bool flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
153.                 W, i - 1);
154.             if (flag)
155.             {
156.                 return true;
157.             }
158.             if (W > weights[i])
159.             {
160.                 //see if W-weight[i] can be achieved with rest of the weights
161.                 return this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W - weights[i], i - 1);
162.             }
163.             return false;
164.         }

Code Snippet

263. [TestCategory(Constants.DynamicProgramming)]
264.         [TestMethod]
265.         public void SubsetSum_NoRepetition_KnapsackSimpliedProblemTests()
266.         {
267.             int[] weights = new int[] { 7, 5, 4, 4, 1 };
268.             List<int> bag = null;
269.             bool flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 10, knapsack: out bag);
270.             Assert.IsTrue(flag);
271.             Assert.IsTrue(bag.Contains(5));
272.             Assert.IsTrue(bag.Contains(4));
273.             Assert.IsTrue(bag.Contains(1));
274.             Assert.IsTrue(bag.Count == 3);
275.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 3, knapsack: out bag);
276.             Assert.IsFalse(flag);
277.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 7, knapsack: out bag);
278.             Assert.IsTrue(flag);
279.             Assert.IsTrue(bag.Contains(7));
280.             Assert.IsTrue(bag.Count == 1);
281.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 1, knapsack: out bag);
282.             Assert.IsTrue(flag);
283.             Assert.IsTrue(bag.Contains(1));
284.             Assert.IsTrue(bag.Count == 1);
285.  
286.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Tabulated_Eager(weights, 10);
287.             Assert.IsTrue(flag);
288.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Tabulated_Eager(weights, 3);
289.             Assert.IsFalse(flag);
290.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Tabulated_Eager(weights, 7);
291.             Assert.IsTrue(flag);
292.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Tabulated_Eager(weights, 1);
293.             Assert.IsTrue(flag);
294.  
295.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(weights, 10);
296.             Assert.IsTrue(flag);
297.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(weights, 3);
298.             Assert.IsFalse(flag);
299.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(weights, 7);
300.             Assert.IsTrue(flag);
301.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_DP_Memoization_Lazy(weights, 1);
302.             Assert.IsTrue(flag);
303.  
304.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 10);
305.             Assert.IsTrue(flag);
306.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 3);
307.             Assert.IsFalse(flag);
308.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 7);
309.             Assert.IsTrue(flag);
310.             flag = this.SubsetSum_NoRepetition_KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 1);
311.             Assert.IsTrue(flag);
312.  
313.  
314.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 10, knapsack: out bag);
315.             Assert.IsTrue(flag);
316.             Assert.IsTrue(bag.Contains(5));
317.             Assert.IsTrue(bag.Contains(4));
318.             Assert.IsTrue(bag.Contains(1));
319.             Assert.IsTrue(bag.Count == 3);
320.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 3, knapsack: out bag);
321.             Assert.IsFalse(flag);
322.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 7, knapsack: out bag);
323.             Assert.IsTrue(flag);
324.             Assert.IsTrue(bag.Contains(7));
325.             Assert.IsTrue(bag.Count == 1);
326.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 1, knapsack: out bag);
327.             Assert.IsTrue(flag);
328.             Assert.IsTrue(bag.Contains(1));
329.             Assert.IsTrue(bag.Count == 1);
330.  
331.             weights = new int[] { 11, 8, 7, 6, 5 };
332.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 20, knapsack: out bag);
333.             Assert.IsTrue(bag.Contains(8));
334.             Assert.IsTrue(bag.Contains(7));
335.             Assert.IsTrue(bag.Contains(5));
336.             Assert.IsTrue(bag.Count == 3);
337.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 27, knapsack: out bag);
338.             Assert.IsFalse(flag);
339.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 11, knapsack: out bag);
340.             Assert.IsTrue(flag);
341.             Assert.IsTrue(bag.Contains(11));
342.             Assert.IsTrue(bag.Count == 1);
343.             flag = this.SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(weights, 5, knapsack: out bag);
344.             Assert.IsTrue(flag);
345.             Assert.IsTrue(bag.Contains(5));
346.             Assert.IsTrue(bag.Count == 1);
347.  
348.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 20, knapsack: out bag);
349.             Assert.IsTrue(bag.Contains(8));
350.             Assert.IsTrue(bag.Contains(7));
351.             Assert.IsTrue(bag.Contains(5));
352.             Assert.IsTrue(bag.Count == 3);
353.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 27, knapsack: out bag);
354.             Assert.IsFalse(flag);
355.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 11, knapsack: out bag);
356.             Assert.IsTrue(flag);
357.             Assert.IsTrue(bag.Contains(11));
358.             Assert.IsTrue(bag.Count == 1);
359.             flag = this.SubsetSum_NoRepetition_KnapsackRecursive(weights, 5, knapsack: out bag);
360.             Assert.IsTrue(flag);
361.             Assert.IsTrue(bag.Contains(5));
362.             Assert.IsTrue(bag.Count == 1);
363.         }